Медиана двух отсортированных массивов может выглядеть как простейшая задача в 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
Проблема и ошибки
Одна из самых сложных частей этой простой проблемы - это возможность решить все тестовые наборы. Вот несколько типичных ошибок, которые допускают кандидаты:
- Итерации по всему массиву
- Забывая, что массив отсортирован
- Нахождение медианы на массиве размером m + n
Когда вы посещаете такие вопросы, всегда помните, что вам не нужно объединять массивы вместе. Постановка проблемы требует только медианы. Это означает, что вы можете вернуть медиану, и все будет готово. Медиана может быть достигнута без необходимости полного объединения обоих массивов. Опять же, вам нужно объединить массивы, но не обязательно делать это полностью.
Логика объединения двух массивов в отсортированном порядке различается для «отсортированных» и «несортированных» массивов. В этой задаче вся идея сортировки упрощена. Почему? В постановке задачи указаны отсортированные массивы. Итак, если вы потратите время на сортировку массива, вы можете растеряться во время собеседования. Вместо этого используйте преимущества сортированного массива. И продолжай.
Псевдокод
Вот простой псевдокод, который поможет вам найти медиану.
- Найдите длину обоих массивов
- Найдите среднее положение. Здесь учтите, что после объединения длина массива может быть четной или нечетной.
- Инициализируйте два указателя, i и j, для каждого массива соответственно.
- На основе значения и, если достигнуто среднее положение, создайте результирующий массив. С каждым значением будет увеличиваться указатель i или указатель j.
- Когда один из массивов полностью повторен, а среднее положение не достигнуто, повторите итерацию оставшегося массива.
- В тот момент, когда ваш указатель 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.
Удачного кодирования!