Java實作 LeetCode 4 尋找兩個有序數組的中位數

1. 尋找兩個有序數組的中位數

給定兩個大小為 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

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/median-of-two-sorted-arrays

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

PS：

這道題讓我們求兩個有序數組的中位數，而且限制了時間複雜度為O(log (m+n))，看到這個時間複雜度，自然而然的想到了應該使用二分查找法來求解。那麼回顧一下中位數的定義，如果某個有序數組長度是奇數，那麼其中位數就是最中間那個，如果是偶數，那麼就是最中間兩個數字的平均值。這裡對于兩個有序數組也是一樣的，假設兩個有序數組的長度分别為m和n，由于兩個數組長度之和 m+n 的奇偶不确定，是以需要分情況來讨論，對于奇數的情況，直接找到最中間的數即可，偶數的話需要求最中間兩個數的平均值。為了簡化代碼，不分情況讨論，我們使用一個小trick，我們分别找第 (m+n+1) / 2 個，和 (m+n+2) / 2 個，然後求其平均值即可，這對奇偶數均适用。加入 m+n 為奇數的話，那麼其實 (m+n+1) / 2 和 (m+n+2) / 2 的值相等，相當于兩個相同的數字相加再除以2，還是其本身。

這裡我們需要定義一個函數來在兩個有序數組中找到第K個元素，下面重點來看如何實作找到第K個元素。首先，為了避免産生新的數組進而增加時間複雜度，我們使用兩個變量i和j分别來标記數組nums1和nums2的起始位置。然後來處理一些邊界問題，比如當某一個數組的起始位置大于等于其數組長度時，說明其所有數字均已經被淘汰了，相當于一個空數組了，那麼實際上就變成了在另一個數組中找數字，直接就可以找出來了。還有就是如果K=1的話，那麼我們隻要比較nums1和nums2的起始位置i和j上的數字就可以了。難點就在于一般的情況怎麼處理？因為我們需要在兩個有序數組中找到第K個元素，為了加快搜尋的速度，我們要使用二分法，對K二分，意思是我們需要分别在nums1和nums2中查找第K/2個元素，注意這裡由于兩個數組的長度不定，是以有可能某個數組沒有第K/2個數字，是以我們需要先檢查一下，數組中到底存不存在第K/2個數字，如果存在就取出來，否則就指派上一個整型最大值。如果某個數組沒有第K/2個數字，那麼我們就淘汰另一個數字的前K/2個數字即可。有沒有可能兩個數組都不存在第K/2個數字呢，這道題裡是不可能的，因為我們的K不是任意給的，而是給的m+n的中間值，是以必定至少會有一個數組是存在第K/2個數字的。最後就是二分法的核心啦，比較這兩個數組的第K/2小的數字midVal1和midVal2的大小，如果第一個數組的第K/2個數字小的話，那麼說明我們要找的數字肯定不在nums1中的前K/2個數字，是以我們可以将其淘汰，将nums1的起始位置向後移動K/2個，并且此時的K也自減去K/2，調用遞歸。反之，我們淘汰nums2中的前K/2個數字，并将nums2的起始位置向後移動K/2個，并且此時的K也自減去K/2，調用遞歸即可。

——一位大佬留下的(奧裡給！！！)

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int left = (m + n + 1) / 2;
        int right = (m + n + 2) / 2;
        return (findKth(nums1, 0, nums2, 0, left) + findKth(nums1, 0, nums2, 0, right)) / 2.0;
    }
    //i: nums1的起始位置 j: nums2的起始位置
    public int findKth(int[] nums1, int i, int[] nums2, int j, int k){
        if( i >= nums1.length) return nums2[j + k - 1];//nums1為空數組
        if( j >= nums2.length) return nums1[i + k - 1];//nums2為空數組
        if(k == 1){
            return Math.min(nums1[i], nums2[j]);
        }
        int midVal1 = (i + k / 2 - 1 < nums1.length) ? nums1[i + k / 2 - 1] : Integer.MAX_VALUE;
        int midVal2 = (j + k / 2 - 1 < nums2.length) ? nums2[j + k / 2 - 1] : Integer.MAX_VALUE;
        if(midVal1 < midVal2){
            return findKth(nums1, i + k / 2, nums2, j , k - k / 2);
        }else{
            return findKth(nums1, i, nums2, j + k / 2 , k - k / 2);
        }        
    }
}