Leetcode（4）——尋找兩個正序數組的中比特數

題目

給定兩個大小分別為 $m$ 和 $n$ 的正序（從小到大）數組 $nums1$ 和 $nums2$。請你找出並返回這兩個正序數組的 中比特數 。

算法的時間複雜度應該為 $O(log(m+n))$。

示例 1：

輸入：nums1 = [1,3], nums2 = [2]
輸出：2.00000
解釋：合並數組 = [1,2,3] ，中比特數 2

示例 2：

輸入：nums1 = [1,2], nums2 = [3,4]
輸出：2.50000
解釋：合並數組 = [1,2,3,4] ，中比特數 (2 + 3) / 2 = 2.5

提示：

• nums1.length == m
• nums2.length == n
• $0$ <= m <= $1000$
• $0$ <= n <= $1000$
• $1$ <= m + n <= $2000$
• $-10^6$ <= nums1[i], nums2[i] <= $10^6$

題解

合並再查找等其他方法就不寫了，時間複雜度達不到要求且簡單

​​  使用歸並的方式，合並兩個有序數組，得到一個大的有序數組。大的有序數組的中間比特置的元素，即為中比特數。

• 不需要合並兩個有序數組，只要找到中比特數的比特置即可。由於兩個數組的長度已知，因此中比特數對應的兩個數組的下標之和也是已知的。維護兩個指針，初始時分別指向兩個數組的下標 $0$ 的比特置，每次將指向較小值的指針後移一比特（如果一個指針已經到達數組末尾，則只需要移動另一個數組的指針），直到到達中比特數的比特置。
• 假設兩個有序數組的長度分別為 $m$ 和 $n$，上述兩種思路的複雜度如何？

​​  第一種思路的時間複雜度是 $O(m+n)$，空間複雜度是 $O(m+n)$。第二種思路雖然可以將空間複雜度降到 $O(1)$，但是時間複雜度仍是 $O(m+n)$。

方法一：二分查找

思路

​​  如果對時間複雜度的要求有 $\log$，通常都需要用到二分查找，這道題也可以通過二分查找實現。

​​  根據中比特數的定義，當 $m+n$ 是奇數時，中比特數是兩個有序數組中的第 $(m+n+1)/2$ 個元素，當 $m+n$ 是偶數時，中比特數是兩個有序數組中的第 $(m+n)/2$ 個元素和第 $(m+n)/2+1$ 個元素的平均值。
​​  因此，這道題可以轉化成：尋找兩個有序數組中的第 $k$ 小的數，當其中 $m+n$ 是奇數時，$k$ 為 $(m+n)/2+1$，當其中 $m+n$ 是偶數時，$k$ 為 $(m+n)/2$ 和 $(m+n)/2+1$。

具體算法思路如下：

​​  假設兩個有序數組分別是 $\text{A}$ 和 $\text{B}$。要找到第 $k$ 個元素，我們可以比較 $\text{A}[k/2-1]$ 和 $\text{B}[k/2-1]$，其中 $/$ 錶示整數除法。
​​  由於 $\text{A}[k/2-1]$ 和 $\text{B}[k/2-1]$ 的前面分別有 $\text{A}[0..k/2-2]$ 和 $\text{B}[0..k/2-2]$，即 $k/2-1$ 個元素，對於 $\text{A}[k/2-1]$ 和 $\text{B}[k/2-1]$ 中的較小值，最多只會有 $(k/2-1)+(k/2-1)\le k-2$ 個元素比它小，那麼它就不能是第 $k$ 小的數了。

因此我們可以歸納出三種情况：

• 如果 $\text{A}[k/2-1]<\text{B}[k/2-1]$，則比 $\text{A}[k/2-1]$ 小或等於的數最多只有 $\text{A}$ 的前 $k/2-1$ 個數和 $\text{B}$ 的前 $k/2-1$ 個數，即比 $\text{A}[k/2-1]$ 小的數最多只有 $k-2$ 個，因此 $\text{A}[k/2-1]$ 不可能是第 $k$ 個數，$\text{A}[0]$ 到 $\text{A}[k/2-1]$ 也都不可能是第 $k$ 個數，$\text{A}[0]$ 到 $\text{A}[k/2-1]$ 可以全部排除。
• 如果 $\text{A}[k/2-1]>\text{B}[k/2-1]$，則可以排除 $\text{B}[0]$ 到 $\text{B}[k/2-1]$。
• 如果 $\text{A}[k/2-1]=\text{B}[k/2-1]$，則可以歸入第一種情况處理。

可以看到，比較 $\text{A}[k/2-1]$ 和 $\text{B}[k/2-1]$ 之後，可以排除 $k/2$ 個不可能是第 $k$ 小的數，查找範圍縮小了一半。同時，我們將在排除後的新數組上繼續進行二分查找，並且根據我們排除數的個數，减少 $k$ 的值，這是因為我們排除的數都不大於第 $k$ 小的數。

有以下三種情况需要特殊處理：

• 如果 $\text{A}[k/2-1]$ 或者 $\text{B}[k/2-1]$ 越界，那麼我們可以選取對應數組中的最後一個元素。在這種情况下，我們必須根據排除數的個數减少 $k$ 的值，而不能直接將 $k$ 减去 $k/2$。
• 如果一個數組為空，說明該數組中的所有元素都被排除，我們可以直接返回另一個數組中第 $k$ 小的元素。
• 如果 $k=1$，我們只要返回兩個數組首元素的最小值即可。

例子

用一個例子說明上述算法。假設兩個有序數組如下：

兩個有序數組的長度分別是 $4$ 和 $9$，長度之和是 $13$，中比特數是兩個有序數組中的第 $7$ 個元素，因此需要找到第 $k=7$ 個元素。

比較兩個有序數組中下標為 $k/2-1=2$ 的數，即 $\text{A}[2]$ 和 $\text{B}[2]$，如下面所示：

由於 $\text{A}[2]>\text{B}[2]$，因此排除 $\text{B}[0]$ 到 $\text{B}[2]$，即數組 $\text{B}$ 的下標偏移（offset）變為 $3$，同時更新 $k$ 的值：$k=k-k/2=4$。

下一步尋找，比較兩個有序數組中下標為 $k/2-1=1$ 的數，即 $\text{A}[1]$ 和 $\text{B}[4]$，如下面所示，其中方括號部分錶示已經被排除的數。

由於 $\text{A}[1]<\text{B}[4]$，因此排除 $\text{A}[0]$ 到 $\text{A}[1]$，即數組 $\text{A}$ 的下標偏移變為 $2$，同時更新 $k$ 的值：$k=k-k/2=2$。

下一步尋找，比較兩個有序數組中下標為 $k/2-1=0$ 的數，即比較 $\text{A}[2]$ 和 $\text{B}[3]$，如下面所示，其中方括號部分錶示已經被排除的數。

由於 $\text{A}[2]=\text{B}[3]$，根據之前的規則，排除 $\text{A}$ 中的元素，因此排除 $\text{A}[2]$，即數組 $\text{A}$ 的下標偏移變為 $3$，同時更新 $k$ 的值： $k=k-k/2=1$。

由於 $k$ 的值變成 $1$，因此比較兩個有序數組中的未排除下標範圍內的第一個數，其中較小的數即為第 $k$ 個數，由於 $\text{A}[3]>\text{B}[3]$，因此第 $k$ 個數是 $\text{B}[3]=4$。

代碼實現

Leetcode 官方題解：

class Solution {
    
public:
    int getKthElement(const vector<int>& nums1, const vector<int>& nums2, int k) {
    
        /* 主要思路：要找到第 k (k>1) 小的元素，那麼就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 進行比較 * 這裏的 "/" 錶示整除 * nums1 中小於等於 pivot1 的元素有 nums1[0 .. k/2-2] 共計 k/2-1 個 * nums2 中小於等於 pivot2 的元素有 nums2[0 .. k/2-2] 共計 k/2-1 個 * 取 pivot = min(pivot1, pivot2)，兩個數組中小於等於 pivot 的元素共計不會超過 (k/2-1) + (k/2-1) <= k-2 個 * 這樣 pivot 本身最大也只能是第 k-1 小的元素 * 如果 pivot = pivot1，那麼 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把這些元素全部 "删除"，剩下的作為新的 nums1 數組 * 如果 pivot = pivot2，那麼 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把這些元素全部 "删除"，剩下的作為新的 nums2 數組 * 由於我們 "删除" 了一些元素（這些元素都比第 k 小的元素要小），因此需要修改 k 的值，减去删除的數的個數 */

        int m = nums1.size();
        int n = nums2.size();
        int index1 = 0, index2 = 0;

        while (true) {
    
            // 邊界情况
            if (index1 == m)
                return nums2[index2 + k - 1];
            if (index2 == n)
                return nums1[index1 + k - 1];
            if (k == 1)
                return min(nums1[index1], nums2[index2]);

            // 正常情况
            int newIndex1 = min(index1 + k / 2 - 1, m - 1);
            int newIndex2 = min(index2 + k / 2 - 1, n - 1);
            int pivot1 = nums1[newIndex1];
            int pivot2 = nums2[newIndex2];
            if (pivot1 <= pivot2) {
    
                k -= newIndex1 - index1 + 1;
                index1 = newIndex1 + 1;
            } else {
    
                k -= newIndex2 - index2 + 1;
                index2 = newIndex2 + 1;
            }
        }
    }

    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    
        int totalLength = nums1.size() + nums2.size();
        if (totalLength % 2 == 1)
            return getKthElement(nums1, nums2, (totalLength + 1) / 2);
        else
            return (getKthElement(nums1, nums2, totalLength / 2) + getKthElement(nums1, nums2, totalLength / 2 + 1)) / 2.0;
    }
};

複雜度分析

時間複雜度：$O(log(m+n))$，其中 $m$ 和 $n$ 分別是數組 ${\text{nums}}_1$ 和 ${\text{nums}}_2$ 的長度。初始時有 $k=(m+n)/2$ 或 $k=(m+n)/2+1$，每一輪循環可以將查找範圍减少一半，因此時間複雜度是 $O(\log (m+n))$。
空間複雜度：$O(1)$

方法二：二分查找+劃分數組

思路

​​  為了使用劃分的方法解决這個問題，需要理解「中比特數的作用是什麼」，如果理解了中比特數的劃分作用，就很接近答案了。。在統計中，中比特數被用來：

將一個集合劃分為兩個長度相等的子集，其中一個子集中的元素總是大於另一個子集中的元素。

首先，在任意比特置 $i$ 將 $\text{A}$ 劃分成兩個部分：

由於 $\text{A}$ 中有 $m$ 個元素， 所以有 $m+1$ 種劃分的方法（$i\in [0,m]$）。

$\text{len}(\text{left\_A})=i,\text{len}(\text{right\_A})=m-i$
注意：當 $i=0$ 時，$\text{left\_A}$ 為空集， 而當 $i=m$ 時, $\text{right\_A}$ 為空集。

采用同樣的方式，在任意比特置 $j$ 將 $\text{B}$ 劃分成兩個部分：

將 $\text{left\_A}$ 和 $\text{left\_B}$ 放入一個集合，並將 $\text{right\_A}$ 和 $\text{right\_B}$ 放入另一個集合。 再把這兩個新的集合分別命名為 $\text{left\_part}$ 和 $\text{right\_part}$：

當 $\text{A}$ 和 $\text{B}$ 的總長度是偶數時，如果可以確認：

• $\text{len}(\text{left\_part})=\text{len}(\text{right\_part})$
• $\max (\text{left\_part})\le \min (\text{right\_part})$

那麼，$\{\text{A},\text{B}\}$ 中的所有元素已經被劃分為相同長度的兩個部分，且前一部分中的元素總是小於或等於後一部分中的元素。中比特數就是前一部分的最大值和後一部分的最小值的平均值：
$$\text{median}=\frac{\text{max}(\text{left}\_\text{part})+\text{min}(\text{right}\_\text{part})}{2}$$

當 $\text{A}$ 和 $\text{B}$ 的總長度是奇數時，如果可以確認：

• $\text{len}(\text{left\_part})=\text{len}(\text{right\_part})+1$
• $\max (\text{left\_part})\le \min (\text{right\_part})$

那麼，$\{\text{A},\text{B}\}$ 中的所有元素已經被劃分為兩個部分，前一部分比後一部分多一個元素，且前一部分中的元素總是小於或等於後一部分中的元素。中比特數就是前一部分的最大值：
$$\text{median}=\text{max}(\text{left}\_\text{part})$$

第一個條件對於總長度是偶數和奇數的情况有所不同，但是可以將兩種情况合並。第二個條件對於總長度是偶數和奇數的情况是一樣的。

要確保這兩個條件，只需要保證：

• $i+j=m-i+n-j$（當 $m+n$ 為偶數）或 $i+j=m-i+n-j+1$（當 $m+n$ 為奇數）。等號左側為前一部分的元素個數，等號右側為後一部分的元素個數。將 $i$ 和 $j$ 全部移到等號左側，我們就可以得到 $i+j=\frac{m+n+1}{2}$。這裏的分數結果只保留整數部分。
• $0\le i\le m$，$0\le j\le n$。如果我們規定 $\text{A}$ 的長度小於等於 $\text{B}$ 的長度，即 $m\le n$。這樣對於任意的 $i\in [0,m]$，都有 $j=\frac{m+n+1}{2}-i\in [0,n]$，那麼我們在 $[0,m]$ 的範圍內枚舉 $i$ 並得到 $j$，就不需要額外的性質了。
  • 如果 $\text{A}$ 的長度較大，那麼我們只要交換 $\text{A}$ 和 $\text{B}$ 即可。
  • 如果 $m>n$，那麼得出的 $j$ 有可能是負數。
• $\text{B}[j-1]\le \text{A}[i]$ 以及 $\text{A}[i-1]\le \text{B}[j]$，即前一部分的最大值小於等於後一部分的最小值。

為了簡化分析，假設 $\text{A}[i-1],\text{B}[j-1],\text{A}[i],\text{B}[j]$ 總是存在。對於 $i=0$、$i=m$、$j=0$、$j=n$ 這樣的臨界條件，我們只需要規定 $\text{A}[-1]=\text{B}[-1]=-\infty$，$A[m]=\text{B}[n]=\infty$ 即可。這也是比較直觀的：當一個數組不出現在前一部分時，對應的值為負無窮，就不會對前一部分的最大值產生影響；當一個數組不出現在後一部分時，對應的值為正無窮，就不會對後一部分的最小值產生影響。

所以我們需要做的是：

在 $[0,m]$ 中找到 $i$，使得：
$\text{B}[j-1]\le \text{A}[i]$ 且 $\text{A}[i-1]\le \text{B}[j]$，其中 $j=\frac{m+n+1}{2}-i$

我們證明它等價於：

在 $[0,m]$ 中找到最大的 $i$，使得：
$\text{A}[i-1]\le \text{B}[j]$，其中 $j=\frac{m+n+1}{2}-i$

這是因為：

• 當 $i$ 從 $0\sim m$ 遞增時，$\text{A}[i-1]$ 遞增，$\text{B}[j]$ 遞减，所以一定存在一個最大的 $i$ 滿足 $\text{A}[i-1]\le \text{B}[j]$；
• 如果 $i$ 是最大的，那麼說明 $i+1$ 不滿足。將 $i+1$ 帶入可以得到 $\text{A}[i]>\text{B}[j-1]$，也就是 $\text{B}[j-1]<\text{A}[i]$，就和我們進行等價變換前 $i$ 的性質一致了（甚至還要更好）。

因此我們可以對 $i$ 在 $[0,m]$ 的區間上進行二分搜索，找到最大的滿足 $\text{A}[i-1]\le \text{B}[j]$ 的 $i$ 值，就得到了劃分的方法。此時，劃分前一部分元素中的最大值，以及劃分後一部分元素中的最小值，才可能作為就是這兩個數組的中比特數。

代碼實現

Leetcode 官方題解：

class Solution {
    
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    
        if (nums1.size() > nums2.size()) {
    
            return findMedianSortedArrays(nums2, nums1);
        }
        
        int m = nums1.size();
        int n = nums2.size();
        int left = 0, right = m;
        // median1：前一部分的最大值
        // median2：後一部分的最小值
        int median1 = 0, median2 = 0;

        while (left <= right) {
    
            // 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]
            // 後一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]
            int i = (left + right) / 2;
            int j = (m + n + 1) / 2 - i;

            // nums_im1, nums_i, nums_jm1, nums_j 分別錶示 nums1[i-1], nums1[i], nums2[j-1], nums2[j]
            int nums_im1 = (i == 0 ? INT_MIN : nums1[i - 1]);
            int nums_i = (i == m ? INT_MAX : nums1[i]);
            int nums_jm1 = (j == 0 ? INT_MIN : nums2[j - 1]);
            int nums_j = (j == n ? INT_MAX : nums2[j]);

            if (nums_im1 <= nums_j) {
    
                median1 = max(nums_im1, nums_jm1);
                median2 = min(nums_i, nums_j);
                left = i + 1;
            } else {
    
                right = i - 1;
            }
        }

        return (m + n) % 2 == 0 ? (median1 + median2) / 2.0 : median1;
    }
};

複雜度分析

時間複雜度：$O(\log \min (m,n)))$，其中 $m$ 和 $n$ 分別是數組 ${\text{nums}}_1$ 和 ${\text{nums}}_2$ 的長度。查找的區間是 $[0,m]$，而該區間的長度在每次循環之後都會减少為原來的一半。所以，只需要執行 $\log m$ 次循環。由於每次循環中的操作次數是常數，所以時間複雜度為 $O(\log m)$。由於我們可能需要交換 ${\text{nums}}_1$ 和 ${\text{nums}}_2$ 使得 $m\le n$ 且我們只對較短的數組進行了二分查找，因此時間複雜度是 $O(\log \min (m,n)))$。
空間複雜度：$O(1)$