Существует два отсортированных массива nums1 и nums2 размером m и n соответственно.
Найдите медиану двух отсортированных массивов. Общая сложность выполнения должна быть O(log (m+n)).
Вы можете предположить, что nums1 и nums2 не могут быть одновременно пустыми.
Пример 1:
nums1 = [1, 3] nums2 = [2] The median is 2.0
Пример 2:
nums1 = [1, 2] nums2 = [3, 4] The median is (2 + 3)/2 = 2.5
I. o (M + n) решение в зависимости от сложности по времени
Давайте объясним, что такое медиана
As follows: [3, 4, 5], then the median of these numbers is 4 [3, 4, 5, 6], then the median of these numbers is (4 + 5) / 2 = 4.5
Сначала я не заметил временной сложности, но, согласно решению O (M + n), это заняло у меня много времени, вероятно, потому, что я долгое время не обращался к алгоритму.
2. Решение дихотомии
В соответствии с приведенным выше объяснением медианы и для упорядоченного массива nums 1 [M], num2 [n], приведенных в названии. Можно подумать, что в конце концов часть цифр 1 должна быть слева от медианы, а часть баллов должна быть справа от медианы. Num2-это то же самое.
Таким образом, мы можем разделить nums1 и nums2 на два массива после слияния.
nums1[0],...,nums1[i-1] | nums1[i] ... nums1[m-1] nums2[0],...,nums2[j-1] | nums2[j] ... nums2[m-1]
Это также можно рассматривать как следующее
nums1[0],...,nums1[i-1],nums2[0],...,nums2[j-1] | nums1[i] ... nums1[m-1],nums2[j] ... nums2[m-1]
Общее количество левых и правых массивов может быть нечетным или четным. Итак, правило таково: если это Нечетное число , то слева на одно больше, чем справа, если это так Четные числа , то левая и правая стороны равны.
Давайте поговорим о взаимосвязи между I и J Номером левого массива t = (int) (M + N + 1)/2 j – i.
Как только вы поймете взаимосвязь между I и j, вам нужно определить медиану Понять условие порядка массива. Видно, что при выполнении условия медианы максимальное число слева равно leftmax меньше Наименьшего числа справа rightmin И количество массивов слева должно быть равно количеству массивов справа или на один больше, чем количество массивов справа.
Вот самое важное В соответствии с приведенным выше рядом условий, что нам нужно сделать сейчас, это выбрать подходящее I с помощью дихотомии, а затем получить медиану
Также рассмотрим граничную задачу, которая прокомментирована в следующем коде
Код выглядит следующим образом:
class Solution{
/**
* @param Integer[] $nums1
* @param Integer[] $nums2
* @return Float
*/
function findMedianSortedArrays($nums1, $nums2) {
$m = count($nums1);
$n = count($nums2);
//If $m > $n, the following $J may be less than 0. That is, the inequality (t = (int) (M + N + 1) / 2 mentioned above. j = t - i.)
if($m>$n) return $this->findMedianSortedArrays($nums2,$nums1);
$t = (int)(($m+$n+1)/2);
$i = 0;
$j = 0;
/**To understand the meaning of the following two groups of Max, min*/
$leftmax = 0; // maximum value of left array
$rightmin = 0; // minimum value of right array
$IMAX = $m; // right boundary of dichotomy
$Imin = 0; // left boundary of dichotomy
while($iMax >= $iMin){
// dichotomy
$i = (int)(($iMax+$iMin)/2);
$j = $t-$i;
If ($I > 0 & & $J < $n & & $nums1 [$I-1] > $nums2 [$J]) {// with array ordering, you can compare only once
$iMax=$i-1;
}Elseif ($J > 0 & & $I < $M & & $nums1 [$I] < nums2 [$J-1]) {// you can only compare once by using array ordering
$iMin=$i+1;
}Else {// two points to the last best position
if ($i==0){
$leftMax = $nums2[$j-1];
}elseif ($j==0){
$leftMax = $nums1[$i-1];
}else {
$leftMax = max($nums2[$j-1],$nums1[$i-1]);
}
If (($m + $n)% 2 = = 1) {// array sum is odd
return $leftMax;
}
//Arrays and are odd
if ($i == $m){
$rightMin = $nums2[$j];
}elseif ($j == $n){
$rightMin = $nums1[$i];
}else {
$rightMin = min($nums2[$j],$nums1[$i]);
}
return ($leftMax+$rightMin)/2;
}
}
}
}резюме
Способность объяснять проблемы нуждается в дальнейшем совершенствовании. Если у вас есть какие-либо вопросы, пожалуйста, общайтесь в приватной обстановке.