两个排好序的数组nums1和nums2，长度分别为m和n。找到这两个数组的中位数，如果是偶数，则中位数是上下中位数的平均值。

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

暴力求解

按照惯例先来个最简单也最粗暴的方法，将两个数组合并为一个数组，然后根据数组的索引找到中位数。

由于两个数组都是排好序的，则可以使用两个指针进行一边比较元素的大小一边放入第三个数组中，代码如下：

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
public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] num3 = new int[nums1.length+nums2.length];
        int i = 0;
        int j = 0;
        int index = 0;
        double median = 0;
        while (i<nums1.length && j<nums2.length){
            if (nums1[i] < nums2[j]){
                num3[index++] = nums1[i];
                i++;
            }else {
                num3[index++] = nums2[j];
                j++;
            }
        }
        while (i < nums1.length){
            num3[index++] = nums1[i];
            i++;
        }
        while (j < nums2.length){
            num3[index++] = nums2[j];
            j++;
        }
        if (num3.length%2 == 0){
            median = (num3[num3.length/2] + num3[num3.length/2 - 1]) / 2.0;
        }else {
            median = num3[num3.length/2];
        }
        return median;
    }
}

利用折半查找的思想

在进行思路解读前，先介绍两个概念，

  • 概念1：某个数组中有一半的元素不超过数组的中位数，有一半的元素不小于中位数（如果数组中元素个数是偶数，那么这里的一半并不是严格意义的1/2）
  • 概念2：如果我们去掉数组比中位数小的k个数，再去掉比中位数大的k个数，得到的子数组的中位数和原来的中位数相同

弯路

折半的思路是nums1的中位数med1和nums2的中位数med2做比较(如果数组是偶数，则中位数是上中位数和下中位数之和的平均值)，有3中比较结果：
1、med1 == med2 则med1就是两个数组的中位数
2、med1 < med2 则中位数只可能出现在nums1[nums1.length/2 - 1]nums[nums1.length]和nums2[0]nums2[nums2.length - nums1.length/2 - 1]中。
3、med1 > med2 则中位数只可能出现在nums1[0]nums1[nums1.length/2]和nums2[nums2.length-nums1.length/2]nums2[nums2.length]区间中。

这里假设nums1的长度小于等于nums2.length，由上面的概念2得知，每次减去的个数应该是两个数组折半的较小值。

按照这个思路去敲代码，发现代码尼玛越写越长，考虑的情况越来越多，如两个数组一个是奇数一个是偶数；一个数组只有两个元素并且另一个数组只有一个元素，或者另一个数组是多个元素(奇偶也不定)，各种情况中位数都不一样，(网上有很多帖子是用上面的思路解决的，那是因为他们遇到偶数的情况取的中位数是上中位数或者下中位数，而本题中却要上下中位数的平均值，这就要求需要保留并且去比较上下中位数，__因为这两个数字可能来自于同一个数组，也可能来自两个数组__这种情况就比较繁琐，很容易漏掉某种情况)。撸到半夜都没有搞定，感觉可能不是这么回事，还是google下吧。

扩展问题至查找第k个元素

由于按照上面的思路撸了两百多行代码都没有搞定，感觉必有蹊跷，然后google下，发现有同命相连者，观其思路的核心思想为
将其转化为去找两个数组的从小到大排的第k个数。两个数组共有m+n个数，若m+n是奇数，那么就是找第(m+n)/2+1个数，偶数的话就是找第(m+n)/2个数和第(m+n)/2+1个数的平均数。转换成找第k个元素之后，在二分查找时就避开了奇数偶数情况不同的问题，只管去第k个元素。

具体思路如下：
假设要在数组A和数组B中查找第k个数(假设A的长度m不大于B的长度n，这里k一定不大于m+n)。也就是找A和B的第k个数。(很显然，数列“前x个数中的最后一个数”就是数列的“第x个数”。所以找第x个数和找前x个数是一样的。因为一但确定了前x个数，这些数的最后一个数就是第x个数)。

先假定最终的前k个数中有一半(k/2)在A中，另一半(k-k/2)在B中。当然，如果A中总个数m少于k/2，只好假定最终的前k个数中有m个在A中，另外k-m个在B中。

做好上面的假定之后，根据之前的假定，A中的在前k个数中的元素的最后一个数是第pa个数，B中的在前k个数中的数的最后一个数叫第pb个数。
1、如果第pa数等于第pb数，那么最终的前k个数的最后一个数一定等于第pa数（是pa还是pb无所谓了），也就是说最终的第k个数就是第pa数。
2、如果第pa数大于第pb数，那么说明，我所假定的B中目前属于前k个数的数确实是属于最终的前k个数，并且后面还有部分数也属于。我所假定的A中目前属于前k个数的数不一定都属于最终的前k个数。好了，于是我就把B中确实是属于最终的前k个数的这pb个数（即第pb和第pb之前的这些数）切掉，变成B’。问题就变为去找A和B’中的前k-pb个数。
3、如果第pa数小于第pb数，那么说明，我所假定的A中目前属于前k个数的数确实是属于最终的前k个数，并且后面还有部分数也属于（有可能后面已经没数了）。我所假定的B中目前属于前k个数的数不一定都属于最终的前k个数。好了，于是我就把A中确实是属于最终的前k个数的这pa个数（即第pa和第pa之前的这些数，有可能就是A中所有的数）切掉，变成了A’（可能是空的）。问题变为去找A’和B中的前k-pa个数。

代码如下：

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
public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length = nums1.length + nums2.length;
        if (length % 2 == 0){
            return (findKth(nums1, nums2, length/2) + findKth(nums1, nums2, length/2 + 1))/2.0;
        }else {
            return findKth(nums1, nums2, length/2 + 1);
        }
    }

    public static int findKth(int[] arr1, int[] arr2, int k){
        // 编码技巧：在算法中，你会假定许多东西，比如两个同等地位的数组，
        // 假定一个比另一个长，那么在编码的时候，
        // 完全没有必要将对称的情况重写一边对称的代码，而是应该将参数反过来递归调用一次！
        if (arr1.length > arr2.length){
            return findKth(arr2, arr1, k);
        }
        // arr1 为空
        if (arr1.length == 0){
            return arr2[k - 1];
        }
        if (k == 1){
            return arr1[0] > arr2[0] ? arr2[0] : arr1[0];
        }
        int pos1 = k/2 < arr1.length ? k/2 : arr1.length;
        int pos2 = k - pos1;
        if (arr1.length == 0){
            return arr2[k - 1];
        }
        if (arr1[pos1 - 1] > arr2[pos2 - 1]){
            // copyOfRange的区间是[from, to)
            arr2 = Arrays.copyOfRange(arr2, pos2, arr2.length);
            return findKth(arr1, arr2, k - pos2);
        }else if (arr1[pos1 - 1] < arr2[pos2 - 1]){
            arr1 = Arrays.copyOfRange(arr1, pos1, arr1.length);
            return findKth(arr1, arr2, k - pos1);
        }else {
            return arr1[pos1 - 1];
        }
    }
}