寻找两个有序数组的中位数

寻找两个有序数组的中位数

Administrator 267 2019-10-21

思路：

  1. 数组nums[]的中位数即数组第(1 + nums.length)/2大的数，若数组为偶数，则中位数为两个中间值的和除以2；
  2. 两个数组的中位数即为两个数组的第（nums1.length + nums2.length）/2大的数。
  3. 定理一： 先将两个数组以第k大的数为边界分为两份，即为nums1_left, nums1_right, nums2_left, nums2_right,且有nums1_left.length + nums2_left.length == k 。
  4. 当要找第k大的数时，只要去掉k - 1位数，剩下的最小值即为第k大的数
  5. 比较两个数组中第k / 2大的数，较小的那个数所在的数组0 - k / 2位可以去掉，原因是min(nums1[k / 2], nums2[k / 2])一定小于两个数组的第k大的数。
  6. 证明：
    1. 设： 两个数组中第k大的数为nums[k]。
    2. 定理一： 将两个数组以第k大的数为边界分为两份，即为nums1_left, nums1_right, nums2_left, nums2_right，且有nums1_left.length + nums2_left.length == k
    3. 反证法： 假设结果不成立，即 min(nums1[k / 2], nums2[k / 2]) > nums[k]，显然max(nums1[k / 2], nums2[k / 2]) > nums[k]
    4. 即min(nums1[k / 2], nums2[k / 2]) 第nums[k / 2] 位于 k / 2之前，即nums1_left.length < k / 2, nums2_left.length < k / 2
    5. 因为第四点，所以nums1_left.length + nums2_left.length < k / 2 + k / 2 == k 与定理一相矛盾，证毕。
  7. 总结： 只要不断去掉两个数组第k / 2个数，直到k == 1。此时只要比较剩下两个数组的最小值即为结果。

实现：

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int total  = nums1.length + nums2.length;
        if (total % 2 == 0) {
            int left = findKthNumber(nums1, 0, nums2, 0, total / 2);
            int right = findKthNumber(nums1, 0, nums2, 0, total / 2 + 1);

            return (left + right) / 2.0;
        }
        return findKthNumber(nums1, 0, nums2, 0, total / 2 + 1);
    }
    /**
     * 找从数组1从i开始、数组2从j开始的第k大的数
     *
     * @param nums1 数组1
     * @param i 数组1起始位置
     * @param nums2 数组2
     * @param j 数组2起始位置
     * @param k 第k大的数
     * @return 找到的结果
     */
    private int findKthNumber(int[] nums1, int i, int[] nums2, int j, int k) {
        if (nums1.length - i > nums2.length - j) {
            return findKthNumber(nums2, j, nums1, i, k);
        }
        if (nums1.length == i) {
            return nums2[j + k - 1];
        }
        if (k == 1) {
            return  Math.min(nums1[i], nums2[j]);
        }

        int si = Math.min(i + k / 2, nums1.length);
        int sj = j + k / 2;

        if (nums1[si - 1] > nums2[sj - 1])
            return findKthNumber(nums1, i, nums2, sj, k - k / 2);
        else
            return findKthNumber(nums1, si, nums2 , j, k - (si - i));
    }

}
算法