4. 寻找两个正序数组的中位数

Problem: 4. 寻找两个正序数组的中位数

思路

一开始看到这道题，我想到的是利用快速排序的分区操作来找出数组第k大元素这个操作，但是使用朴素算法实际上需要$O(N)$的时间复杂度，而且没有利用到数组已经正序这个信息。

要利用数组已经正序的信息，我们可以想到中位数一定是合并起来数组的第n/2 个元素或第n/2和第n/2 + 1个元素的平均值。我们的任务转为了求出求出这两个有序数组中的第k大的元素，即第k个元素。

考虑到需要$O(N)$的时间复杂度，自然而然需要用到分治或者二分的思想。我们可以参考分区操作找出第k大元素的思想，逐渐排除一部分元素，直到问题规模小到可以直接解决为止。

这里就需要用一点小trick了。我们的目标是要找到第k个元素，出于分治考虑，我们考察两个数组各自的第k/2个元素（不足则取最大的那个），比较它们的大小，较小的记为a，另一个记为b。显然，这两个元素加上之前的元素总的元素个数小于等于k个，那么就可以分几种情况考虑：

1. 如果k较大（不在边界情况），那么我们知道a左边的数都小于它本身，又小于b，所以a左边的数都不可能是第k大的数。所以我们去掉这个范围，并修改现在的k值。至于b左边的数，我们仍无法直接判断，因为还要考虑到a右边的数。
2. 如果一个数组已经空了，那么另一个数组的第k个数就是我们要找的数。
3. 如果k已经等于1了，那么我们a就是我们要找的数。

Code

[]

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length1 = nums1.length, length2 = nums2.length;
        int totalLength = length1 + length2;
        if (totalLength % 2 == 1) {
            int midIndex = totalLength / 2;
            return (double) getKthElement(nums1, nums2, midIndex + 1);
        } else {
            int midIndex1 = totalLength / 2 - 1, midIndex2 = totalLength / 2;
            return (double)(getKthElement(nums1, nums2, midIndex1 + 1) + getKthElement(nums1, nums2, midIndex2 + 1)) / 2.0;
        }
    }

    public int getKthElement(int[] nums1, int[] nums2, int k) {
        int length1 = nums1.length, length2 = nums2.length;
        int index1 = 0, index2 = 0;
        int kthElement = 0;

        while (true) {
            if (index1 == length1) {
                return nums2[index2 + k - 1];
            }
            if (index2 == length2) {
                return nums1[index1 + k - 1];
            }
            if (k == 1) {
                return Math.min(nums1[index1], nums2[index2]);
            }
            
            // 正常情况
            int half = k / 2;
            int newIndex1 = Math.min(index1 + half, length1) - 1;
            int newIndex2 = Math.min(index2 + half, length2) - 1;
            int pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2];
            if (pivot1 <= pivot2) {
                k -= (newIndex1 - index1 + 1);
                index1 = newIndex1 + 1;
            } else {
                k -= (newIndex2 - index2 + 1);
                index2 = newIndex2 + 1;
            }
        }
    }
}