No.004：Median of Two Sorted Arrays，no.004median
題目：
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays.
The overall run time complexity should be O(log (m+n)).
Example1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
官方難度：
Hard
翻譯：
兩個已排序數組，大小分別是m和n，找出這兩個數組的中位數。
整個算法的時間復雜度是O(log(m+n))
例子：
[1,3]和[2]，中位數是2.0
[1,2]和[3,4]，中位數是2.5
思路：
1.乍一看不難，因為已排序，把兩個數組合並成一個有序數組，每次比較兩數組當前指針的數字大小，小的放進新數組，得到結果數組之後，取中位數。但是時間復雜度是O(m+n)。
2.根據1中的思路，不需要取結果數組，每次遍歷加以此判斷，遍歷至中位數的地點直接拿值計算就行了，而且還能夠節約一份數組空間。但是時間復雜度是O((m+n)/s)，仍然不達標。
3.取2個有序數組的中位數比較，去掉相對較小的那個數的數組，中位數前面的值，以及相對較大的那個數的數組，中位數後面的值。使用遞歸，將剩余部分數組作為下次遞歸的初始值。時間復雜度是O(log(m+n))。
解題中可能遇到的困難：
1.每次去掉的數組，大小必須相同，若是不同，往長度小的那一方靠攏。如：[1,2,3]和[4,5,6,7,8]，下一次遞歸的數組，應該是[2,3]和[4,5,6,7]，而不是[2,3]和[4,5,6]。
2.當去掉數組的長度為0時，需要特殊考慮，分2種情況：1是存在長度為1的數組；2是存在長度為2的數組，且在中位數比較的過程中是較小的一方。
3.以上兩種情況，2比較容易考慮，而1又分為4種情況，在代碼中會描述清楚。
4.需要考慮當一個數組被镂空了的情況。
解題代碼：
![]()
1 // 因為兩數組分別有序，用類二分查找法尋找中位數，時間復雜度O(log(m+n))
2 private static double method3(int[] array1, int[] array2) {
3 // 優先判斷，一個數組用完的情況
4 if (array1.length == 0 || array2.length == 0) {
5 int[] tempArray;
6 if (array1.length == 0) {
7 tempArray = array2;
8 } else {
9 tempArray = array2;
10 }
11 // 直接返回單個有序數組的中位數，奇偶情況可以用一個式子表達
12 return (tempArray[tempArray.length / 2] + tempArray[(tempArray.length - 1) / 2]) / 2.0;
13 }
14 // 兩個數組都存在的情況
15 int medianIndex1 = (array1.length - 1) / 2;
16 int medianIndex2 = (array2.length - 1) / 2;
17 // 操作數組統一賦值
18 int[] tempMedianMinArray;
19 int[] tempMedianMaxArray;
20 // 操作數組中位數索引標志
21 int minIndex;
22 int maxIndex;
23 // 兩數組統一賦值處理
24 if (array1[medianIndex1] < array2[medianIndex2]) {
25 tempMedianMinArray = array1;
26 tempMedianMaxArray = array2;
27 minIndex = medianIndex1;
28 maxIndex = medianIndex2;
29 } else {
30 tempMedianMinArray = array2;
31 tempMedianMaxArray = array1;
32 minIndex = medianIndex2;
33 maxIndex = medianIndex1;
34 }
35 // 要去掉的數組賦值
36 int[] arrayToReduceFromBegin = Arrays.copyOf(tempMedianMinArray, minIndex);
37 int[] arrayToReduceToEnd = Arrays.copyOfRange(tempMedianMaxArray, tempMedianMaxArray.length - maxIndex,
38 tempMedianMaxArray.length);
39 // 要去掉的數組長度不為0
40 if (!(arrayToReduceFromBegin.length == 0 || arrayToReduceToEnd.length == 0)) {
41 // 兩數組每次減去的數組長度必須相同
42 int reduceLength = Math.min(arrayToReduceFromBegin.length, arrayToReduceToEnd.length);
43 int[] nextArray1 = Arrays.copyOfRange(tempMedianMinArray, reduceLength, tempMedianMinArray.length);
44 int[] nextArray2 = Arrays.copyOf(tempMedianMaxArray, tempMedianMaxArray.length - reduceLength);
45 return method3(nextArray1, nextArray2);
46 } else {
47 // 存在2種情況：情況1.存在長度為1的數組；情況2.存在長度為2且中位數比較較小的那一方
48 // 先考慮情況2，包括部分情況1也適用
49 if (tempMedianMinArray.length == 2) {
50 // 小數組去最前的1位，大數組去最後的1位
51 int[] nextArray1 = Arrays.copyOfRange(tempMedianMinArray, 1, 2);
52 int[] nextArray2 = Arrays.copyOf(tempMedianMaxArray, tempMedianMaxArray.length - 1);
53 return method3(nextArray1, nextArray2);
54 } else {
55 // 情況1
56 // 兩數組長度都為1，特殊考慮
57 if (tempMedianMinArray.length == 1 && tempMedianMaxArray.length == 1) {
58 return (tempMedianMinArray[0] + tempMedianMaxArray[0]) / 2.0;
59 }
60 // 統一操作賦值
61 int[] tempArray1;
62 int[] tempArray2;
63 if (tempMedianMinArray.length == 1) {
64 tempArray1 = tempMedianMinArray;
65 tempArray2 = tempMedianMaxArray;
66 } else {
67 tempArray1 = tempMedianMaxArray;
68 tempArray2 = tempMedianMinArray;
69 }
70 // 之後有4中情況
71 if (tempArray1[0] < tempArray2[tempArray2.length / 2]) {
72 if (tempArray1[0] < tempArray2[0]) {
73 // 形如[1]和[6,7,8]
74 tempArray1 = new int[] {};
75 // 去尾
76 tempArray2 = Arrays.copyOf(tempArray2, tempArray2.length - 1);
77 } else {
78 // 形如[7]和[6,8,9]
79 tempArray2 = Arrays.copyOfRange(tempArray2, 1, tempArray2.length - 1);
80 }
81 } else {
82 if (tempArray1[0] > tempArray2[tempArray2.length - 1]) {
83 // 形如[9]和[6,7,8]
84 tempArray1 = new int[] {};
85 // 去頭
86 tempArray2 = Arrays.copyOfRange(tempArray2, 1, tempArray2.length);
87 } else {
88 // 形如[8]和[6,7,9]
89 tempArray2 = Arrays.copyOfRange(tempArray2, 1, tempArray2.length - 1);
90 }
91 }
92 return method3(tempArray1, tempArray2);
93 }
94 }
View Code
測試代碼地址：
https://github.com/Gerrard-Feng/LeetCode/blob/master/LeetCode/src/com/gerrard/algorithm/hard/Q004.java
LeetCode題目地址：
https://leetcode.com/problems/median-of-two-sorted-arrays/
PS：源碼中，有我在思路裡提到的，前2種方法，即時間復雜度分別為O(m+n)和O((m+n)/2)的。
PPS：如有不正確或提高效率的方法，歡迎留言，謝謝！
