這道演算法題太簡單？你忽略了時間複雜度的要求！_演算法愛好者

這道演算法題太簡單？你忽略了時間複雜度的要求！

演算法愛好者2019-10-03 13:29:58

（給演算法愛好者加星標，修煉程式設計內功）

來源：五分鐘學演算法

這道題目很有意思！

忽略時間複雜度的要求的話，so easy ！加上了時間複雜度的要求，so hard！

而很多小夥伴一開始沒有注意時間複雜度的要求，還很納悶：這個難度是困難嗎？怎麼感覺比簡單難度的的還簡單啊。

題目來源於 LeetCode 上第 4 號問題：尋找兩個有序陣列的中位數。題目難度為 Hard，目前通過率為 35.6% 。

題目描述

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

題目解析

題目說的是給兩個排好序的陣列，讓你求出這兩個陣列中所有元素按從小到大排列，排在中間的元素，時間複雜度也是有要求的，O(log(m + n))，m 和 n 分別是這兩個陣列的長度。

這裡提到了時間複雜度為 O(log(m+n)) ，很容易想到的就是二分查詢，所以現在要做的就是在兩個排序陣列中進行二分查詢。

具體思路如下，將問題 轉化為在兩個陣列中找第 K 個小的數 。

求中位數，其實就是求第 k 小數的一種特殊情況。

首先在兩個陣列中分別找出第 k/2 大的數，再比較這兩個第 k/2 大的數，這裡假設兩個陣列為 A ，B。

那麼比較結果會有下面幾種情況：

A[k/2] = B[k/2],那麼第 k 大的數就是 A[k/2]
A[k/2] > B[k/2],那麼第 k 大的數肯定在 A[0:k/2+1] 和 B[k/2:] 中，這樣就將原來的所有數的總和減少到一半了，再在這個範圍裡面找第 k/2 大的數即可，這樣也達到了二分查詢的區別了。
A[k/2]

舉個例子：

A = [1,3,4,7]
B = [1,2,3,4,5,6,7,8,9,10]

這兩個陣列總共 14 個數字，是偶數，因此要找出它們的第 15 / 2 = 7 小的數字與第 16 / 2 = 8 小的數字。

下面以找出第 7 小的數字為例進行說明。

k = 7

k / 2 = 3

分別找出它們的第 k/2 大的數為 4 與 3 。（注意的是如果 k 是奇數，則向下取整）

根據這兩個數將 A、B 陣列劃分為兩部分。

然後對比這兩個數，上邊陣列中的 4 和下邊陣列中的 3，如果哪個小，就表明該陣列的前 k/2 個數字都不是第 k 小數字，可以捨棄。

捨棄掉的那三個數字肯定是在 最前面 的數字，因此一開始是要查詢第 7 小的數字，現在變成了要查詢第 7 - 3 = 4 小的數字。

同樣的進行取兩個陣列的 k/2 數字進行區域劃分與比較。

捨棄掉 A 陣列的前部分之後，兩個陣列又發生了變化。

現在變成了去查詢第 4 - 2 = 2 小的數字了。

此時出現了一個 特殊情況 ：A 陣列的 分割元素 與 B陣列的 分割元素 相等，都為 4。

這種情況隨意捨棄一個就行！程式碼編寫的時候注意邊界判斷即可。

捨棄之後，問題簡單了：查詢兩個陣列中最小的那個數字。

只需要比較兩個陣列的開頭數字就行了。（別忘記，這兩個陣列都是遞增有序的）

所以第 7 小的數字是 4 。

同樣的操作，可以查找出第 8 小的數字是 5。

所以，A 陣列和 B 陣列的中位數是 （4 + 5）÷ 2 = 4.5。

如果你對上面的圖片描述還是有點疑惑的話，強烈建議將下面的動畫完整的看完。

動畫描述

程式碼實現

//@author:windliang
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int n = nums1.length;
    int m = nums2.length;
    int left = (n + m + 1) / 2;
    int right = (n + m + 2) / 2;
    //一個小技巧：將偶數和奇數的情況合併，如果是奇數，會求兩次同樣的 k 。
    return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5;  
}

    private int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
        int len1 = end1 - start1 + 1;
        int len2 = end2 - start2 + 1;
        //讓 len1 的長度小於 len2，這樣就能保證如果有陣列空了，一定是 len1 
        if (len1 > len2) return getKth(nums2, start2, end2, nums1, start1, end1, k);
        if (len1 == 0) return nums2[start2 + k - 1];

        if (k == 1) return Math.min(nums1[start1], nums2[start2]);

        int i = start1 + Math.min(len1, k / 2) - 1;
        int j = start2 + Math.min(len2, k / 2) - 1;

        if (nums1[i] > nums2[j]) {
            return getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
        }
        else {
            return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
        }
    }