你的位置:首页 > Java教程

[Java教程]No.004:Median of Two Sorted Arrays

题目:

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     // 要去掉的数组长度不为040     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         // 情况156         // 两数组长度都为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:如有不正确或提高效率的方法,欢迎留言,谢谢!