Медиана двух отсортированных массивов может выглядеть как простейшая задача в Leetcode, помеченная как сложная. Есть много причин, по которым многим трудно решить эту проблему.

Постановка задачи

Для двух отсортированных массивов nums1 и nums2 размера m и n соответственно вернуть медианное значение двух отсортированных массивов.

Общая сложность времени выполнения должна быть O(log (m+n)).

Пример 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Пример 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Пример 3:

Input: nums1 = [0,0], nums2 = [0,0]
Output: 0.00000

Пример 4:

Input: nums1 = [], nums2 = [1]
Output: 1.00000

Пример 5:

Input: nums1 = [2], nums2 = []
Output: 2.00000

Проблема и ошибки

Одна из самых сложных частей этой простой проблемы - это возможность решить все тестовые наборы. Вот несколько типичных ошибок, которые допускают кандидаты:

  1. Итерации по всему массиву
  2. Забывая, что массив отсортирован
  3. Нахождение медианы на массиве размером m + n

Когда вы посещаете такие вопросы, всегда помните, что вам не нужно объединять массивы вместе. Постановка проблемы требует только медианы. Это означает, что вы можете вернуть медиану, и все будет готово. Медиана может быть достигнута без необходимости полного объединения обоих массивов. Опять же, вам нужно объединить массивы, но не обязательно делать это полностью.

Логика объединения двух массивов в отсортированном порядке различается для «отсортированных» и «несортированных» массивов. В этой задаче вся идея сортировки упрощена. Почему? В постановке задачи указаны отсортированные массивы. Итак, если вы потратите время на сортировку массива, вы можете растеряться во время собеседования. Вместо этого используйте преимущества сортированного массива. И продолжай.

Псевдокод

Вот простой псевдокод, который поможет вам найти медиану.

  1. Найдите длину обоих массивов
  2. Найдите среднее положение. Здесь учтите, что после объединения длина массива может быть четной или нечетной.
  3. Инициализируйте два указателя, i и j, для каждого массива соответственно.
  4. На основе значения и, если достигнуто среднее положение, создайте результирующий массив. С каждым значением будет увеличиваться указатель i или указатель j.
  5. Когда один из массивов полностью повторен, а среднее положение не достигнуто, повторите итерацию оставшегося массива.
  6. В тот момент, когда ваш указатель i или j достигнет средней позиции, вычислите носитель и верните значение

Решение Javascript

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
  
    let m = nums1.length;
    let n = nums2.length;
    
    let len = m + n;
    
    let res = new Array();
    
    let i = 0;
    let j = 0;
    let k = 0;
    
    let pos = ((m+n) % 2 != 0) ? Math.floor((m+n)/2) : ((m+n)/2)
    let pos1 =  ((m+n) % 2 != 0) ? Math.floor((m+n)/2) : (((m+n)/2) - 1)
  
   while(i<m && j<n && k<=pos){
     
       if(nums1[i]<nums2[j]){
           res[k]=nums1[i];
           i=i+1;
       }
       else
       {
            res[k]=nums2[j];
           j=j+1;
       }
        k=k+1;
   }
    
   while(i<m && k <= pos){
        res[k]=nums1[i];
        i=i+1;
        k=k+1;
   }
   while(j<n && k <= pos){
       res[k]=nums2[j];
       j=j+1;
       k=k+1;
   }
   let val = res[pos] + res[pos1];
   return val/2  
};

Вышеупомянутое решение работает в соответствии с описанным псевдокодом. Эта проблема не использует ни одну из библиотек Javascript. Вместо этого мы построили собственную логику для итерации и нахождения медианы двух отсортированных массивов.

Примечание: это решение решает все тестовые случаи, предлагаемые leetcode.

Удачного кодирования!