Имея два отсортированных массива 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 ]