Median of two Sorted Arrays · 數據結構與算法/leetcode/lintcode題解

# Median of two Sorted Arrays ### Source - leetcode: [Median of Two Sorted Arrays | LeetCode OJ](https://leetcode.com/problems/median-of-two-sorted-arrays/) - lintcode: [(65) Median of two Sorted Arrays](http://www.lintcode.com/en/problem/median-of-two-sorted-arrays/) ### Problem There are two sorted arrays *A* and *B* of size *m* and *n* respectively. Find the **median** of the two sorted arrays. #### Example Given `A=[1,2,3,4,5,6]` and `B=[2,3,4,5]`, the median is `3.5`. Given `A=[1,2,3]` and `B=[4,5]`, the median is `3`. #### Challenge The overall run time complexity should be O(log (m+n)). ### 題解1 - 歸并排序何謂"Median"? 由題目意思可得即為兩個數組中一半數據比它大，另一半數據比它小的那個數。詳見 [中位數 - 維基百科，自由的百科全書](http://zh.wikipedia.org/wiki/%E4%B8%AD%E4%BD%8D%E6%95%B8)。簡單粗暴的方法就是使用歸并排序的思想，挨個比較兩個數組的值，取小的，最后分奇偶長度返回平均值或者中位值。 ### Java1 - merge sort with equal length ~~~ class Solution { /** * @param A: An integer array. * @param B: An integer array. * @return: a double whose format is *.5 or *.0 */ public double findMedianSortedArrays(int[] A, int[] B) { if ((A == null || A.length == 0) && (B == null || B.length == 0)) { return -1.0; } int lenA = (A == null) ? 0 : A.length; int lenB = (B == null) ? 0 : B.length; int len = lenA + lenB; /* merge sort */ int indexA = 0, indexB = 0, indexC = 0; int[] C = new int[len]; // case1: both A and B have elements while (indexA < lenA && indexB < lenB) { if (A[indexA] < B[indexB]) { C[indexC++] = A[indexA++]; } else { C[indexC++] = B[indexB++]; } } // case2: only A has elements while (indexA < lenA) { C[indexC++] = A[indexA++]; } // case3: only B has elements while (indexB < lenB) { C[indexC++] = B[indexB++]; } // return median for even and odd cases int indexM1 = (len - 1) / 2, indexM2 = len / 2; if (len % 2 == 0) { return (C[indexM1] + C[indexM2]) / 2.0; } else { return C[indexM2]; } } } ~~~ ### Java2 - space optimization ~~~ class Solution { /** * @param A: An integer array. * @param B: An integer array. * @return: a double whose format is *.5 or *.0 */ public double findMedianSortedArrays(int[] A, int[] B) { if ((A == null || A.length == 0) && (B == null || B.length == 0)) { return -1.0; } int lenA = (A == null) ? 0 : A.length; int lenB = (B == null) ? 0 : B.length; int len = lenA + lenB; int indexM1 = (len - 1) / 2, indexM2 = len / 2; int m1 = 0, m2 = 0; /* merge sort */ int indexA = 0, indexB = 0, indexC = 0; // case1: both A and B have elements while (indexA < lenA && indexB < lenB) { if (indexC > indexM2) { break; } if (indexC == indexM1) { m1 = Math.min(A[indexA], B[indexB]); } if (indexC == indexM2) { m2 = Math.min(A[indexA], B[indexB]); } if (A[indexA] < B[indexB]) { indexA++; } else { indexB++; } indexC++; } // case2: only A has elements while (indexA < lenA) { if (indexC > indexM2) { break; } if (indexC == indexM1) { m1 = A[indexA]; } if (indexC == indexM2) { m2 = A[indexA]; } indexA++; indexC++; } // case3: only B has elements while (indexB < lenB) { if (indexC > indexM2) { break; } if (indexC == indexM1) { m1 = B[indexB]; } if (indexC == indexM2) { m2 = B[indexB]; } indexB++; indexC++; } // return median for even and odd cases if (len % 2 == 0) { return (m1 + m2) / 2.0; } else { return m2; } } } ~~~ ### 源碼分析使用歸并排序的思想做這道題不難，但是邊界條件的處理比較鬧心，使用歸并排序帶輔助空間的做法實現起來比較簡單，代碼也短。如果不使用額外空間并做一定優化的話需要多個 if 語句進行判斷，需要注意的是多個 if 之間不能使用 else ，因為`indexM1`和`indexM2`有可能相等。 ### 復雜度分析時間復雜度 O(m+n)O(m + n)O(m+n), 空間復雜度為 (m+n)(m + n)(m+n)(使用額外數組), 或者 O(1)O(1)O(1)(不使用額外數組). ### 題解2 - 二分搜索題中已有信息兩個數組均為有序，找中位數的關鍵在于找到第一半大的數，顯然可以使用二分搜索優化。本題是找中位數，其實可以泛化為一般的找第 k 大數，這個輔助方法的實現非常有意義！在兩個數組中找第k大數->找中位數即為找第k大數的一個特殊情況——第(A.length + B.length) / 2 大數。因此首先需要解決找第k大數的問題。這個聯想確實有點牽強... 由于是找第k大數(從1開始)，使用二分法則需要比較A[k/2 - 1]和B[k/2 - 1]，并思考這兩個元素和第k大元素的關系。 1. A[k/2 - 1] <= B[k/2 - 1] => A和B合并后的第k大數中必包含A[0]~A[k/2 -1]，可使用歸并的思想去理解。 1. 若k/2 - 1超出A的長度，則必取B[0]~B[k/2 - 1] ### C++ ~~~ class Solution { public: /** * @param A: An integer array. * @param B: An integer array. * @return: a double whose format is *.5 or *.0 */ double findMedianSortedArrays(vector<int> A, vector<int> B) { if (A.empty() && B.empty()) { return 0; } vector<int> NonEmpty; if (A.empty()) { NonEmpty = B; } if (B.empty()) { NonEmpty = A; } if (!NonEmpty.empty()) { vector<int>::size_type len_vec = NonEmpty.size(); return len_vec % 2 == 0 ? (NonEmpty[len_vec / 2 - 1] + NonEmpty[len_vec / 2]) / 2.0 : NonEmpty[len_vec / 2]; } vector<int>::size_type len = A.size() + B.size(); if (len % 2 == 0) { return ((findKth(A, 0, B, 0, len / 2) + findKth(A, 0, B, 0, len / 2 + 1)) / 2.0); } else { return findKth(A, 0, B, 0, len / 2 + 1); } // write your code here } private: int findKth(vector<int> &A, vector<int>::size_type A_start, vector<int> &B, vector<int>::size_type B_start, int k) { if (A_start > A.size() - 1) { // all of the element of A are smaller than the kTh number return B[B_start + k - 1]; } if (B_start > B.size() - 1) { // all of the element of B are smaller than the kTh number return A[A_start + k - 1]; } if (k == 1) { return A[A_start] < B[B_start] ? A[A_start] : B[B_start]; } int A_key = A_start + k / 2 - 1 < A.size() ? A[A_start + k / 2 - 1] : INT_MAX; int B_key = B_start + k / 2 - 1 < B.size() ? B[B_start + k / 2 - 1] : INT_MAX; if (A_key > B_key) { return findKth(A, A_start, B, B_start + k / 2, k - k / 2); } else { return findKth(A, A_start + k / 2, B, B_start, k - k / 2); } } }; ~~~ ### Java ~~~ class Solution { /** * @param A: An integer array. * @param B: An integer array. * @return: a double whose format is *.5 or *.0 */ public double findMedianSortedArrays(int[] A, int[] B) { if ((A == null || A.length == 0) && (B == null || B.length == 0)) { return -1.0; } int lenA = (A == null) ? 0 : A.length; int lenB = (B == null) ? 0 : B.length; int len = lenA + lenB; // return median for even and odd cases if (len % 2 == 0) { return (findKth(A, 0, B, 0, len/2) + findKth(A, 0, B, 0, len/2 + 1)) / 2.0; } else { return findKth(A, 0, B, 0, len/2 + 1); } } private int findKth(int[] A, int indexA, int[] B, int indexB, int k) { int lenA = (A == null) ? 0 : A.length; if (indexA > lenA - 1) { return B[indexB + k - 1]; } int lenB = (B == null) ? 0 : B.length; if (indexB > lenB - 1) { return A[indexA + k - 1]; } // avoid infilite loop if k == 1 if (k == 1) return Math.min(A[indexA], B[indexB]); int keyA = Integer.MAX_VALUE, keyB = Integer.MAX_VALUE; if (indexA + k/2 - 1 < lenA) keyA = A[indexA + k/2 - 1]; if (indexB + k/2 - 1 < lenB) keyB = B[indexB + k/2 - 1]; if (keyA > keyB) { return findKth(A, indexA, B, indexB + k/2, k - k/2); } else { return findKth(A, indexA + k/2, B, indexB, k - k/2); } } } ~~~ ### 源碼分析本題用非遞歸的方法非常麻煩，遞歸的方法減少了很多邊界的判斷。此題的邊界條件較多，不容易直接從代碼看清思路。首先分析找k大的輔助程序。以 Java 的代碼為例。 1. 首先在主程序中排除 A, B 均為空的情況。 1. 排除 A 或者 B 中有一個為空或者長度為0的情況。如果`A_start > A.size() - 1`，意味著A中無數提供，故僅能從B中取，所以只能是B從`B_start`開始的第k個數。下面的B...分析方法類似。 1. k為1時，無需再遞歸調用，直接返回較小值。如果 k 為1不返回將導致后面的無限循環。 1. 以A為例，取出自`A_start`開始的第`k / 2`個數，若下標`A_start + k / 2 - 1 < A.size()`，則可取此下標對應的元素，否則置為int的最大值，便于后面進行比較，免去了諸多邊界條件的判斷。 1. 比較`A_key > B_key`，取小的折半遞歸調用findKth。接下來分析`findMedianSortedArrays`： 1. 首先考慮異常情況，A, B都為空。 1. A+B 的長度為偶數時返回len / 2和 len / 2 + 1的均值，為奇數時則返回len / 2 + 1 ### 復雜度分析找中位數，K 為數組長度和的一半，故總的時間復雜度為 O(log(m+n))O(\log (m+n))O(log(m+n)). ### Reference - [九章算法 | Median of Two Sorted Arrays](http://www.jiuzhang.com/solutions/median-of-two-sorted-arrays/) - [LeetCode: Median of Two Sorted Arrays 解題報告 - Yu's Garden - 博客園](http://www.cnblogs.com/yuzhangcmu/p/4138184.html)