题目
有两个升序排列的数组nums1和nums2，现在要求出它们合并以后有序数组的中间下标的那个值。
如果合并以后的数组有奇数个元素那么就是中间下标那个值。
如果合并以后的数组有偶数个元素那么就是中间俩值的平均值。
时间复杂度必须是O(log(m+n))
示例
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
思路1
不管三七二十一直接把两个数组合并成一个数组，然后排序，然后取中间值。这种算法的时间复杂度能达到O((n+m)log(n+m))达不到题目要求。
思路2
思维模型是，把合并以后的数组拆分成2个集合，一个集合中任一元素不小于另一集合中任意元素的值，并且这两个集合元素个数要么相等要么差1。判定两个输入的数组一个长度必然大于等于另一个，并设长短数组中各有一个分界点，分界点之下的在整体数组较小部分，分界点以上的都在整体数组的较大部分，也就是说，两个数组中无论哪个数组的分界点上面的元素值都必须大于等于这两个数组的分界点之下的元素值，那么你所要做的就是找到这样的分界点。用二分查找法在长度较小数组中找到这个分界点是本算法的关键，也是时间复杂度的保障。
它的时间复杂度是O(log(m+n))
思路3
设i是从A[0...i-1]这一小段的元素个数，j是从B[0...j-1]这一小段的元素个数，且满足i+j=k，k是要找到的那个值在合并以后数组中的序数，设合并以后的数组为C，则要找的那个值就是C[k-1]。
于是有如果A[i-1]>B[j-1]则C[k-1]必然不在B[0...j-1]中，于是从B中剔除B[0...j-1]，然后此时原来要找的C中的第k个数就变成了第k-j个数了，那么接下来就按照此方法在AB中继续搜寻第k-j个数。
最后如果剩下的元素都不同，那么k最终变成了1，于是取剩下的两数组中的较小的0下标元素值。
如果相同，那么随便取一个值就是要找的那个值。
这里的i和j取的是k的一半。
它的时间复杂度也是O(log(m+n))
思路4
这就是归并排序中的归并步骤嘛，于是就很简单了。它的时间复杂度是O(m+n)，空间复杂度是O(m+n)。
思路5
思路4中的时间复杂度和空间复杂度都有点高，为此可以对其进行优化。用两个指针分别指向2个数组的开头，哪个小就递增哪个指针。再增加一个计数器，每递增一次指针就把计数器值加1，并临时存储数组中该下标对应的值，直到计数器值达到比中位线大1就找到了中间值，它的时间复杂度是O((m+n)/2)。
技巧
取数组中位数一般要根据数组长度是奇数还是偶数分别处理，但是可以不用这样做，可以用统一的方式来处理，具体为：
(array[array.length / 2] + array[(array.length - 1) / 2]) / 2
使用
package com.company;
public class Main {
public static void main(String[] args) {
// write your code here
int[] nums0 = {1,2,3};
int[] nums1 = {5,6};
System.out.println(Solution.findMedianSortedArrays3(nums0,nums1));
}
}
输出
3.0
Process finished with exit code 0
代码实现
package com.company;
public class Solution {
/**
* 我的第一种想法，合并，排序，找出中间index然后相加得到结果。
* 当然这肯定不是最优解，但是它是解。
* 整个算法的复杂度是O(nlogn)
* 因为有堆排序在里面嘛。
* @param nums0
* @param nums1
* @return
*/
static public double findMedianSortedArrays(int[] nums0,int[] nums1) {
if (!(nums0.length >= 1 && nums1.length >= 1)) {
System.out.println("输入数组为空");
return 0;
}
int[] mergedArray = new int[nums0.length + nums1.length];
for (int counter = 0;counter < nums0.length + nums1.length;counter++) {
if (counter < nums0.length)mergedArray[counter] = nums0[counter];
else mergedArray[counter] = nums1[counter - nums0.length];
}
//排序就用堆排序吧。
HeapSort.heapSort0(mergedArray);
if ((nums0.length + nums1.length) % 2 == 0) {
double component0 = mergedArray[(nums0.length + nums1.length) / 2];
double component1 = mergedArray[(nums0.length + nums1.length) / 2 - 1];
double result = (component0 + component1) / 2;
return result;
} else {
double result = mergedArray[(nums0.length + nums1.length) / 2];
return result;
}
}
/**
* 本算法就用LeetCode上面的已经被接受的解决方案来实现
* 这个方法其实就是解方程。这个算法看上去很麻烦，有几个
* 问题。
* 1、为什么是(m+n+1)/2而不是(m+n)/2？
* 因为这样得到的是较小集合中元素的个数而不是下标。
* 2、为什么要选择个数较少的数组进行变动呢？
* 这是因为元素个数少的那个数组带来的变动也少，毕竟这个
* 关系式是一个线性方程，或者说一元一次方程，而元素个
* 数大的那个数组能够容纳这个变动的数量，以至于不会越界。
* 所以i选择较少的那个范围进行变动。
* 3、这个算法的关键是啥？
* 就是那个关系式，即，把两个合并以后的数组分成两个相等
* 的集合。这个关系式只能保证i和j相加等于整个的一半而已。
* 4、边界值
* 首先中位置是肯定存在的，所以如果找到了边界值就没法再
* 继续了，那么要找的那个位置肯定就是那个边界值。对于边
* 界值越界的时候会发现，0越界的意思是说较小的那个数组
* 中的元素在整体的上半部分。max越界的意思是说较小的那
* 个数组全部出现在整体数组的较小值部分。也就是说一旦出
* 现越界就代表整体数组的中间点已经被找到了，就是此时在
* 较长数组中出现的位置了。
* 5、分割点
* 现在设分割点分别为i和j。那么两边的值就分别是A[i-1]、
* A[i]、B[j-1]、B[j]。不满足条件的时候会出现A[i-1]>B[j]
* 或者B[j-1]>A[i]，但是这二者并不会同时出现。为什么呢？
* 因为这是可以证明的拿A[i-1]>B[j]为例，因为A[i]>=A[i-1]，
* B[j]>=B[j-1]，所以A[i]>B[j-1]。所以不满足条件的
* 时候只有一个，并不会同时出现。
* 6、整体数组长度奇偶数不同咋办？
* 偶数的话中间值是两个，奇数的话是一个，这就要分开处理。
* 如果用统一的方式来处理呢？还是不了吧，感觉没多大意义。
* @param nums0
* @param nums1
* @return
*/
static public double findMedianSortedArrays0(int[] nums0,int[] nums1) {
//错误检查
if (nums0.length == 0 && nums1.length != 0)
return (nums1[nums1.length / 2] + nums1[(nums1.length - 1) / 2]) / 2.0;
//这是个技巧，知道了这个以后，你就不用在为数组长度是奇数还是偶数来分别处理了。
if (nums0.length != 0 && nums1.length == 0)
return (nums0[nums0.length / 2] + nums0[(nums0.length - 1) / 2]) / 2.0;
if (nums0.length == 0 && nums1.length == 0)
return 0;
//必须选择两个数组中长度较小的那个。用两个指针指向这两个数组。
int[] smallerArray = nums0;
int[] biggerArray = nums1;
if (nums0.length > nums1.length) {
smallerArray = nums1;
biggerArray = nums0;
}
int smallerSize = smallerArray.length;
int biggerSize = biggerArray.length;
//接下来是在较小的那个数组上面遍历它的分割点，范围是[1,smallerSize]
int lowerPointer = 0;
int higherPointer = smallerSize;
double resultValue = 0;
while (lowerPointer <= higherPointer) {
//由于是有序数组，所以此处应该二分查找法。
// 此处代表较小数组中的较小分组中元素个数。
// 正因为是分割点所以下标smallerDivider-1
// 在较小的一边，而下标smallerDivider在较大的一边。
int smallerDivider = (lowerPointer + higherPointer) / 2;
//这样得到的是较大数组中的对应的元素的下标，
// 并且这个下标是在较小的那一半里面还是较大
// 的那一半里面？我想应该是较大的那一半里面。
// 为什么呢？因为我实际试了一下。
int biggerIndex = (smallerSize + biggerSize + 1) / 2 - smallerDivider;
//为了减少非目的判断的次数，次数先判断非目标条件。
if (smallerDivider > lowerPointer && smallerArray[smallerDivider - 1] > biggerArray[biggerIndex]) {
//因为只有大于区间的左边界才能继续往小缩小范围。
//因为这两个数组都是升序排列的，所以如果想达到
// smallerArray[lowerPointer - 1] < biggerArray[biggerDivider]，
// 还得把smallerDivider往左移才行，因为左边是变小的嘛。
higherPointer = --smallerDivider;
} else if (smallerDivider < higherPointer && biggerArray[biggerIndex - 1] > smallerArray[smallerDivider]) {
//因为只有小于区间的大边界值才能有递增的空间。
//因为只有biggerIndex往左移才能改变这种状态。
lowerPointer = ++smallerDivider;
} else {
//较小的集合中最大的值
int smallerBiggestNumber = 0;
//用数组长度判断会导致思维变得复杂，因为可能会出现2个值，判断起来麻烦得很。
// 如果使用当前下标来判断就会简化很多。所以预期判断
// smallerDivider == smallerSize
// 不如判断biggerIndex == 0的时候
if (smallerDivider == 0) {
//此时说明小数组中没有一个在小半段中，
// 那么小集合中最大的那个值肯定就在大数组中了。
smallerBiggestNumber = biggerArray[biggerIndex - 1];
} else if (biggerIndex == 0) {
//如果是判断用smallerDivider == smallerSize判断的话，
// 就需要判断2个数组中的值来判断哪个更大。此时说明整体中较
// 小的值都在小数组中。由此看来弄清楚边界值的意义很重要。
smallerBiggestNumber = smallerArray[smallerDivider - 1];
} else {
smallerBiggestNumber = smallerArray[smallerDivider - 1] > biggerArray[biggerIndex - 1]?smallerArray[smallerDivider - 1]:biggerArray[biggerIndex - 1];
}
//较大集合中的最小的值
int biggerSmallestNumber = 0;
if (biggerIndex == biggerSize) {
//此时说明数组中的另一半较大的值全在小数组中。
biggerSmallestNumber = smallerArray[smallerDivider];
} else if (smallerDivider == smallerSize) {
//此时说明大集合中最小的那个值肯定在长数组中。
biggerSmallestNumber = biggerArray[biggerIndex];
} else {
biggerSmallestNumber = smallerArray[smallerDivider] > biggerArray[biggerIndex]?biggerArray[biggerIndex]:smallerArray[smallerDivider];
}
if ((smallerSize + biggerSize) % 2 == 0) {
resultValue = (smallerBiggestNumber + biggerSmallestNumber) / 2.0;
} else {
//因为(smallerSize + biggerSize + 1) / 2得到
// 的是整个数组中较大一半中的最小值，并且如果是奇数
// 的话，小集合个数肯定比大集合个数多1.
resultValue = smallerBiggestNumber;
}
break;
}
}
return resultValue;
}
/**
* 这是用分治思想解决问题的方法。
* 分治思想一般都是迭代，递归。
* @param nums0
* @param nums1
* @return
*/
static public double findMedianSortedArrays1(int[] nums0,int[] nums1) {
int targetOrder = (nums0.length + nums1.length) / 2;
if ((nums0.length + nums1.length) % 2 == 0)
return (Solution.findMedianNumber(nums0,0,nums0.length,nums1,0,nums1.length,targetOrder) +
Solution.findMedianNumber(nums0,0,nums0.length,nums1,0,nums1.length,targetOrder + 1))
/ 2.0;
else return Solution.findMedianNumber(nums0,0,nums0.length,nums1,0,nums1.length,targetOrder + 1);
}
/**
* 该方法通过递归的方式分治的策略来寻找下表所指示的那个元素值。
* 实际上是二分查找法的另一种应用。
* 这一招也是我从网上学来的，就是说如果i+j=k,那么如果A[i-1]>B[j-1]，
* 则所要找的第k个数必然不在B[0...j-1]中，于是舍去B[0...j-1]。
* 那么转去A和B[j...]中去寻找。
* 如果到最后的2个值不重复，那必然只会剩下一个值，那个值就是我想要的。
* 如果是重复的值，那么返回任何一个都可以。
* @param A
* @param aStartIndex
* @param B
* @param bStartIndex
* @param targetOrder
* @return
*/
static private int findMedianNumber(int[] A,
int aStartIndex,
int currentALength,
int[] B,
int bStartIndex,
int currentBLength,
int targetOrder) {
//如果数组为空，需要加以判断。
if (currentALength == 0 && currentBLength != 0)return B[bStartIndex + targetOrder - 1];
if (currentALength != 0 && currentBLength == 0)return A[aStartIndex + targetOrder - 1];
if (currentALength == 0 && currentBLength == 0)return 0;
//这样可以总是让指针不越界，即，让A总是指向较短的那个数组，B总是指向较长的那个数组。
if (currentALength > currentBLength)
return Solution.findMedianNumber(B,bStartIndex,currentBLength,A,aStartIndex,currentALength,targetOrder);
//因为每次指针都指向了中间那个值，所以中间那个值会出现两种情况，
// 一种是这两个数相等，另一种是这两个数不等。不等的话最后肯定就
// 只剩下一个了，那剩下的这个就是要找的那个了。
if (targetOrder == 1)
return A[aStartIndex] > B[bStartIndex]?B[bStartIndex]:A[aStartIndex];
//现在设置两个指针分别指向targetOrder/2的位置。较短长度的数组不一定能够达到targetOrder/2的位置。
int aPointer = (targetOrder / 2 > currentALength)?(aStartIndex + currentALength - 1):(aStartIndex + targetOrder / 2 - 1);
//较长的数组才会达到这一位置上。但是需要满足关系当前遍历的两个数组小段的长度之和等于targetOrder/2。
int bPointer = bStartIndex + targetOrder - aPointer + aStartIndex - 2;
if (A[aPointer] < B[bPointer]) {
//此时要找的值肯定不在A里面，于是舍去这一段。
targetOrder -= (aPointer - aStartIndex + 1);
aStartIndex = aPointer + 1;
currentALength = A.length - aStartIndex;
return Solution.findMedianNumber(A,aStartIndex,currentALength,B,bStartIndex,currentBLength,targetOrder);
} else if (A[aPointer] > B[bPointer]) {
targetOrder -= (bPointer - bStartIndex + 1);
bStartIndex = bPointer + 1;
currentBLength = B.length - bStartIndex;
return Solution.findMedianNumber(A,aStartIndex,currentALength,B,bStartIndex,currentBLength,targetOrder);
} else return A[aPointer];
}
/**
* 收到归并排序的启发，这其实就是归并排序中的归并子序列过程。
* 没啥好说的，空间复杂度为O(m+n)，时间复杂度为O(m+n)。
* @param nums0
* @param nums1
* @return
*/
static public double findMedianSortedArrays2(int[] nums0,int[] nums1) {
int[] mergeArray = new int[nums0.length + nums1.length];
int pointer = 0;
int pointer0 = 0;
int pointer1 = 0;
while (pointer0 < nums0.length && pointer1 < nums1.length) {
if (nums0[pointer0] > nums1[pointer1])mergeArray[pointer++] = nums1[pointer1++];
else mergeArray[pointer++] = nums0[pointer0++];
}
while (pointer0 < nums0.length)mergeArray[pointer++] = nums0[pointer0++];
while (pointer1 < nums1.length)mergeArray[pointer++] = nums1[pointer1++];
if (nums0.length + nums1.length == 0)return 0;
else return (mergeArray[(nums0.length + nums1.length) / 2] + mergeArray[(nums0.length + nums1.length - 1) / 2]) / 2.0;
}
/**
* 这是针对findMedianSortedArrays2的改进算法
* 因为findMedianSortedArrays2需要额外的空间
* 现在改用指针和计数器来实现
* 它的时间复杂度是O((m+n)/2)
* @param nums0
* @param nums1
* @return
*/
static public double findMedianSortedArrays3(int[] nums0,int[] nums1) {
if (nums0.length + nums1.length == 0)return 0;
int pointer0 = 0;
int pointer1 = 0;
int counter = 0;
int biggerTargetIndex = (nums0.length + nums1.length) / 2;
int smalllTargetIndex = (nums0.length + nums1.length - 1) / 2;
int biggerTargetValue = 0;
int smallerTargetValue = 0;
while (pointer0 < nums0.length && pointer1 < nums1.length) {
if (nums0[pointer0] > nums1[pointer1]) {
if (counter == smalllTargetIndex)smallerTargetValue = nums1[pointer1];
if (counter == biggerTargetIndex) {
biggerTargetValue = nums1[pointer1];
return (smallerTargetValue + biggerTargetValue) / 2.0;
}
pointer1++;
}
else {
if (counter == smalllTargetIndex)smallerTargetValue = nums0[pointer0];
if (counter == biggerTargetIndex) {
biggerTargetValue = nums0[pointer0];
return (smallerTargetValue + biggerTargetValue) / 2.0;
}
pointer0++;
}
counter++;
}
if (pointer0 < nums0.length) {
if (counter - 1 < smalllTargetIndex)smallerTargetValue = nums0[pointer0 + smalllTargetIndex - counter];
if (counter - 1 < biggerTargetIndex)biggerTargetValue = nums0[pointer0 + biggerTargetIndex - counter];
}
if (pointer1 < nums1.length) {
if (counter - 1 < smalllTargetIndex)smallerTargetValue = nums1[pointer1 + smalllTargetIndex - counter];
if (counter - 1 < biggerTargetIndex)biggerTargetValue = nums1[pointer1 + biggerTargetIndex - counter];
}
return (smallerTargetValue + biggerTargetValue) / 2.0;
}
}
网友评论