Имея два отсортированных массива nums1
и nums2
размера m
и n
соответственно, верните медиану Two отсортированных массивов .
Arr = [🍊,🍊,🍎,🍌,🍊,🍌,🍎,🍊]-›Arr=[🍊,🍊,🍊,🍊,🍌,🍌,🍎,🍎].
Наша функция попытается найти медиану двух отсортированных массивов, объединив их, отсортировав объединенный массив и затем найдя значение медианы.
Не начинайте решать эту проблему, не подумав о наилучшем подходе с точки зрения сложности памяти💾 и времени⌛. Более эффективным подходом было бы использование алгоритма на основе слияния, который объединяет два массива и находит медиану по ходу дела, без необходимости для сортировки всего массива.
function findMedian(nums1, nums2) { var combined = []; var i = 0; var j = 0; // Merge the two arrays while (i < nums1.length && j < nums2.length) { if (nums1[i] < nums2[j]) { combined.push(nums1[i]); i++; } else { combined.push(nums2[j]); j++; } } // Add any remaining elements from nums1 or nums2 while (i < nums1.length) { combined.push(nums1[i]); i++; } while (j < nums2.length) { combined.push(nums2[j]); j++; } // Find the median of the combined array var centerPosition = combined.length / 2; if (combined.length % 2 === 0) { return (combined[centerPosition - 1] + combined[centerPosition]) / 2; } else { return combined[Math.floor(centerPosition)]; } }
Эта функция принимает два отсортированных массива, nums1
и nums2
, и возвращает медиану объединенного массива.
Первое, что делает функция, это инициализирует пустой массив с именем combined
и две переменные i
и j
равными 0. Они будут использоваться для отслеживания текущей позиции в каждом из входных массивов по мере их объединения.
Затем функция входит в цикл while
, который будет выполняться до тех пор, пока i
меньше длины nums1
, а j
меньше длины nums2
. В цикле функция сравнивает элемент в текущей позиции в nums1
(nums1[i]
) с элементом в текущей позиции в nums2
(nums2[j]
). Если nums1[i]
меньше nums2[j]
, функция добавляет nums1[i]
к массиву combined
и увеличивает i
на 1. Если nums1[i]
больше или равно nums2[j]
, функция добавляет nums2[j]
к массиву combined
и увеличивает j
на 1. Этот процесс продолжается до тех пор, пока не достигнут конец одного из входных массивов.
После завершения цикла while
функция проверяет, остались ли какие-либо элементы в nums1
или nums2
, и добавляет их в массив combined
, используя два дополнительных цикла while
.
Наконец, функция определяет медиану массива combined
в зависимости от того, является ли длина массива нечетной или четной. Если длина четная, медиана вычисляется как среднее двух средних элементов (combined[centerPosition - 1]
и combined[centerPosition]
). Если длина нечетная, возвращается средний элемент (combined[Math.floor(centerPosition)]
).
Реальные проблемы
Представьте, что вы создаете программное приложение, которое позволяет пользователям искать и сравнивать арендуемую недвижимость. У каждого объекта есть список удобств, таких как бассейн, тренажерный зал или терраса на крыше. Вы хотите предоставить функцию, позволяющую пользователям искать недвижимость с определенным набором удобств.
Чтобы реализовать эту функцию, вы можете хранить удобства для каждого свойства в отсортированном массиве. Например
const property1 = [ 'gym', 'pool', 'rooftop deck' ]; const property2 = [ 'gym', 'pool' ]; const property3 = [ 'rooftop deck' ];
Чтобы найти свойства с определенным набором удобств, вы можете определить функцию, которая принимает поисковый запрос (также представленный в виде отсортированного массива) и возвращает список свойств, соответствующих запросу. Например:
function findMatchingProperties(query, properties) { const matchingProperties = []; for (const property of properties) { if (findMedian(query, property) === query.length) { matchingProperties.push(property); } } return matchingProperties; } const properties = [ property1, property2, property3 ]; const query = [ 'gym', 'pool' ]; console.log(findMatchingProperties(query, properties)); // [ property1, property2 ]