【LeetCode 經(jīng)典】MedianSortedArrays

前言

在兩個排序數(shù)組中尋找中位數(shù)。這個題目本質(zhì)上二分查找 binarySearch 的變種。需要采用跟二分法類似的思路：先確定一個 median，然后根據(jù)當(dāng)前的狀態(tài)，舍棄一半，在剩下的一半中繼續(xù)尋找。

median 與奇偶性

這個問題是不能回避的。對于一個排序數(shù)組，我們求 median 的時候，其實會根據(jù)數(shù)組的元素個數(shù)分類討論：如果總數(shù)是奇數(shù)，就取數(shù)組的最中間那個元素，對應(yīng)的 index = (n + 1) / 2 ，注意，這里其實有一個小細(xì)節(jié)，即，這里有一個隱含的類型轉(zhuǎn)換：我們把 m.5 轉(zhuǎn)換成了 m 。比如，如果 n = 10，那么得出的 index 應(yīng)該是 5.5，然后轉(zhuǎn)換成 int 之后，就是 index = 5。如果總數(shù)是偶數(shù)，那么就取中間兩個元素求平均數(shù)，也就是：index1 = n / 2; index2 = index1 + 1;。

因此，把問題擴(kuò)展到 median of two sorted array 的時候，我們依然不能回避奇偶性的問題。

二分查找的體現(xiàn)

在排序數(shù)組里面找元素，一般都逃不開二分查找。這相當(dāng)于充分利用了數(shù)組的排序特性。但是，對于兩個數(shù)組，其實直接二分查找讓我們無從下手，因為兩個數(shù)組之間并沒有明確的關(guān)系。所以，我們的二分查找只能針對其中一個數(shù)組 A，然后看看另一個數(shù)組 B 與數(shù)組 A 之間有沒有什么關(guān)系可以找到。
聯(lián)系到，我們想找數(shù)組的中位數(shù)。中位數(shù)的含義，其實就是找到一個數(shù)字，然后讓集合中恰好有一半的元素比中位數(shù)小，恰好有一半的元素比中位數(shù)大。那么把問題拓展到兩個數(shù)組中之后，我們需要做類似的事情：把兩個數(shù)組形成的一個大的集合分成兩半，一半比中位數(shù)小，一半比中位數(shù)大。比如，我們通過二分查找，找到了 A 中的下標(biāo)為 i 的元素，那么，他意味著，A 中有 i 個元素比他小。也就是說，A 對于“小的一半”會貢獻(xiàn) i 個元素。因為我們可以知道，兩個數(shù)組一共有多少個元素，即 count = len1 + len2，那么我們就能知道，“小的一半”一共有多少個元素，即 leftCount = count / 2，進(jìn)而我們就能得出 B 中應(yīng)該有多少個元素參與到“小的一半”。

一些細(xì)節(jié)

1. 對于 A 數(shù)組全員參與和全員不參與兩種情況，我們當(dāng)做特殊情況來處理。在代碼中，會通過 end == -1 和 start == len1 來代表。這兩種情況，我們需要單獨計算 B 對應(yīng)的下標(biāo)。
2. 算法中需要保證 A 的元素不能比 B 多，這樣可以讓 A 無論是全員參與還是全員不參與，B 經(jīng)過計算后得到的 index 都是處于一個合理的值。所以在函數(shù)的開始，會通過 len1 和 len2 的判斷來遞歸一下。

Talk is cheap, show me the code!

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0) {
            return findMedian(nums2);
        } else if (nums2 == null || nums2.length == 0) {
            return findMedian(nums1);
        }

        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }

        int start1 = 0;
        int end1 = nums1.length - 1;

        int len1 = nums1.length;
        int len2 = nums2.length;
        int totalLen = len1 + len2;
        int leftCount = (totalLen + 1) / 2;

        while (start1 <= end1 || end1 == -1 || start1 == len1) {

            int mid1 = (start1 + end1) >>> 1;
            if (end1 == -1) {
                mid1 = -1;
            } else if (start1 == len1) {
                mid1 = len1;
            }
            int mid2 = leftCount - (mid1 + 1) - 1;

            int a1 = getValueSafe(nums1, mid1, Integer.MIN_VALUE);
            int a2 = getValueSafe(nums1, mid1 + 1, Integer.MAX_VALUE);

            int b1 = getValueSafe(nums2, mid2, Integer.MIN_VALUE);
            int b2 = getValueSafe(nums2, mid2 + 1, Integer.MAX_VALUE);

            if (a1 > b2) {
                end1 = mid1 - 1;
            } else if (b1 > a2) {
                start1 = mid1 + 1;
            } else {
                if (totalLen % 2 == 0) {
                    return ((double) Math.max(a1, b1) + (double) Math.min(a2, b2)) / 2;
                } else {
                    return Math.max(a1, b1);
                }
            }
        }
        return 0;
    }

    private double findMedian(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length % 2 == 0) {
            return ((double) (nums[nums.length / 2] + nums[nums.length / 2 - 1])) / 2;
        } else {
            return nums[nums.length / 2];
        }
    }

    private int getValueSafe(int[] nums, int i, int defaultValue) {
        if (i >= 0 && i < nums.length) {
            return nums[i];
        } else {
            return defaultValue;
        }
    }
}