题目

英文

4. Median of Two Sorted Arrays
There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0
Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

中文

4. 寻找两个有序数组的中位数
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0
示例 2:

nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

思路

一下午，还是没解出来尴尬。

代码

官方解题思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
    function findMedianSortedArrays($nums1, $nums2) {
        $count1 = count($nums1);
        $count2 = count($nums2);
        
        //交换$nums1为大一点数组
        if($count2 > $count1)
        {
            $count1 = $count1 + $count2;
            $count2 = $count1 - $count2;
            $count1 = $count1 - $count2;
            $tmp = $nums1;
            $nums1 = $nums2;
            $nums2= $tmp;
        }
    
        $iMin = 0;
        $iMax = $count2;
        $halfLen = intval((($count1 + $count2 +1)/2)) ;
        while($iMin <= $iMax)
        {
            $i = intval((($iMax+$iMin) /2));
            $j = $halfLen -$i;
            if($i < $iMax && $nums1[$j-1] > $nums2[$i])
            {
                $iMin = $i + 1;
            }
            else if($i > $iMin && $nums2[$i-1] > $nums1[$j])
            {
                $iMax = $i-1;
            }
            else {
                $maxLeft = 0;
                if($i == 0){$maxLeft = $nums1[$j-1];}
                elseif($j == 0){$maxLeft =  $nums2[$i-1];}
                else{$maxLeft = max($nums2[$i-1],$nums1[$j-1]);}
                if((($count1 + $count2)%2) == 1) {return $maxLeft;}
                $minRight = 0;
                if($i == $count2){$minRight = $nums1[$j];}
                else if($j == $count1){$minRight = $nums2[$i];}
                else{$minRight = min($nums1[$j], $nums2[$i]);}
                
                return ($maxLeft + $minRight)/2;
            }
        }
        return 0.0;
    }
    
}

思路清晰

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        /**
        如果两个数组的中位数 mid1 < mid2, 则说明合并后的中位数位于 num1.right + num2之间
        否则合并后的中位数位于 nums2.right + nums1 之间 (right 是相对于 mid 而言的) 
        getKth 函数负责找到两个数组合并(假设)后有序的数组中的第 k 个元素, k 从 1 开始计算
        **/   
        if(nums1.length == 0 && nums2.length == 0) return 0.0;
        int m = nums1.length, n = nums2.length;
        // l: 合并后数组的左半部分的最后一个数 r: 合并后数组的右半部分的第一个数
        int l = (m+n+1) / 2; 
        int r = (m+n+2) / 2;
        // 如果 m+n 是奇数 getKth 的返回值是相同的, 是偶数则是合并后数组的中间两个数
        if(l == r) return getKth(nums1, 0, nums2, 0, l);
        return (getKth(nums1, 0, nums2, 0, l) + getKth(nums1, 0, nums2, 0, r)) / 2.0;
    }
    
    private double getKth(int[] nums1, int st1, int[] nums2, int st2, int k) {
        // 边界情况, 如果 nums1数组已经穷尽了, 则只能返回 nums2 中的第 k 个元素
        if(st1 > nums1.length-1) return nums2[st2 + k - 1];
        if(st2 > nums2.length-1) return nums1[st1 + k - 1];
        // 边界情况, k = 1 则返回两个数组中最小的那个
        if(k == 1) return Math.min(nums1[st1], nums2[st2]);
        // 在 nums1 和 nums2 当前范围内找出 mid1 和 mid2 判断舍弃哪半部分
        int mid1 = Integer.MAX_VALUE;
        int mid2 = Integer.MAX_VALUE;
        if(st1 + k/2 - 1 < nums1.length) mid1 = nums1[st1 + k/2 - 1];
        if(st2 + k/2 - 1 < nums2.length) mid2 = nums2[st2 + k/2 - 1];
        // mid1 < mid2 在 nums1.right 和 nums2 之间搜索, 丢掉 k/2 个数.
        if(mid1 < mid2)
            return getKth(nums1, st1 + k/2, nums2, st2, k - k/2);
        else
            return getKth(nums1, st1, nums2, st2 + k/2, k - k/2);
    }
}

自己思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
class Solution {
    function findMedianSortedArrays($nums1, $nums2) {
        $count1 = count($nums1);
        $count2 = count($nums2);
        //第一个数组为0情况
        if($count1 == 0 ) {
            if($count2%2 ==0) {
                return ($nums2[$count2/2-1] + $nums2[($count2/2)])/2;
            } else {
                return $nums2[ceil($count2/2)-1];
            }
        }
        //第二个数组为0情况
        if($count2 == 0 ) {
            if($count1%2 ==0) {
                return ($nums1[$count1/2 -1] + $nums1[($count1/2)])/2;
            } else {
                return $nums1[ceil($count1/2) -1];
            }
        }
        //中位数在两个数组合并以后的位置（从0开始）
        $halfLen = ($count1 + $count2)%2 == 0 ? ($count1 + $count2)/2 -1 :intval(($count1 + $count2)/2) ;
        //交换$nums1为大一点数组
        if($count2 > $count1)
        {
            $count1 = $count1 + $count2;
            $count2 = $count1 - $count2;
            $count1 = $count1 - $count2;
            $tmp = $nums1;
            $nums1 = $nums2;
            $nums2= $tmp;
        }
        $ret = $this->Bsearch($nums1, $nums2, 0,$count2-1, $halfLen);
        return $ret;
    }
    
    //递归查找
    function Bsearch($nums1,$nums2,$start,$end,$halfLen)
    {
        
        //向下取整中位数
        $mid = intval(($start+$end)/2);
        $poision = $halfLen - $mid-1;
        //这里临界值判断
        if($start == $end) {
            //偶数个
            if((count($nums1)+count($nums2))%2==0)
            {
                if($start == 0 ) 
                {
                    if($nums1[$poision] < $nums2[$mid]){
                        echo 1;
                        return ($nums1[$poision] +(isset($nums1[$poision+1]) ? min($nums1[$poision+1], $nums2[$mid]) : $nums2[$mid]))/2; 
                    } 
                    if($nums1[$poision] > $nums2[$mid])
                    {
                        echo 2;
                        return (($nums1[$poision] + (isset($nums1[$poision-1]) ? max($nums1[$poision-1], $nums2[$mid]) : $nums2[$mid]) )/2); 
                    }
                } 
                if($start == (count($nums2) -1)) {
                    //都是临界值时
                    if($nums1[$poision] > $nums2[$mid])
                    {
                        echo 3;
                        return (($nums1[$poision] + (isset($nums1[$poision-1]) ? max($nums1[$poision-1], $nums2[$mid]) : $nums2[$mid]) )/2); 
                    }
                    if($nums1[$poision] < $nums2[$mid])
                    {
                        echo 9;
                        return ($nums1[$poision] +(isset($nums1[$poision+1]) ? min($nums1[$poision+1], $nums2[$mid]) : $nums2[$mid]))/2;
                    }
                }
                echo 5;
                return ((isset($nums1[$poision+1]) ? min($nums2[$mid], $nums1[$poision+1]) : $nums2[$mid])  + $nums1[$poision])/2;
            } else {
                //基数个
                if($start == 0 ) 
                {
                    if($nums1[$poision] > $nums2[$mid]){
                        echo 6;
                        return $nums2[$mid];
                    }
                    echo 11;
                    return $nums1[$poision];
                }
                if($start == count($count2)-1)
                {
                    if($start == $halfLen && $nums1[$poision] < $nums2[$mid])
                    {
                        echo 7;
                        return $nums1[$poision];
                    }
                    echo 8;
                    return $nums1[$poision];
                }
                echo 10;
                echo $poision."\n";
                echo $mid."\n";
                return $nums1[$poision];
            }
        }
        //比对中位数
        if($nums2[$mid] < $nums1[$poision])
        {
            $ret = $this->Bsearch($nums1, $nums2,  (($mid+1 > $end) ? $end : $mid+1), $end, $halfLen);
        } elseif($nums2[$mid] > $nums1[$poision])
        {
            $ret = $this->Bsearch($nums1,$nums2,$start ,(($mid-1 < $start) ? $start : $mid-1), $halfLen);
        }elseif($nums2[$mid] == $nums1[$poision])
        {
            $ret = $nums2[$mid];
        }
        return $ret;
    }
    
}