给定两个大小分别为m和n的正序(从小到大)数组nums1和nums2。请你找出并返回这两个正序数组的中位数。
算法的时间复杂度应该为O(log(m+n))。
示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数(2+3)/2=2.5
提示：
- nums1.length == m
- nums2.length == n
- 0 <= m <= 1000
- 0 <= n <= 1000
- 1 <= m + n <= 2000
- -106 <= nums1[i], nums2[i] <= 106
一、基础思想解法
遍历两个数组，就是一看到题目就想到的那种算法思想，条件很多，又臭又长。时间复杂度: O(m+n), 空间复杂度: O(1)。
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
double median = 0.0;
int m = nums1.length, n = nums2.length;
//分别指向数组nums1和nums2的下标
int mIdx = 0, nIdx = 0,temIdx = 0;
//中位数的位置
int desIdx = (m + n + 1) / 2;
//是否为两个数的中位数
boolean isTwo = (m + n) % 2 == 0;
while(temIdx <= desIdx || isTwo){
temIdx++;
//两个数组进行比较，取最小的那个
if(mIdx < m && nIdx < n && nums1[mIdx] <= nums2[nIdx]){
if(temIdx == desIdx && !isTwo){//如果只有一个中位数，找到直接返回
return nums1[mIdx];
}else if(temIdx == desIdx && isTwo){//如果有两个中位数，并且现在指向了第一个数，把它赋给media
median = nums1[mIdx];
}else if(temIdx == desIdx + 1){//如果有两个中位数，并且现在指向了第二个数，返回结果
return (median + nums1[mIdx]) / 2.0;
}
mIdx++;
}else if(mIdx < m && nIdx < n && nums1[mIdx] > nums2[nIdx]){////两个数组进行比较，取最小的那个
if(temIdx == desIdx && !isTwo){
return nums2[nIdx];
}else if(temIdx == desIdx && isTwo){
median = nums2[nIdx];
}else if(temIdx == desIdx + 1){
return (median + nums2[nIdx]) / 2.0;
}
nIdx++;
}else if(mIdx < m && nIdx == n){//当数组num2已经遍历完，而数据nums1还有数据
if(temIdx == desIdx && !isTwo){
return nums1[mIdx];
}else if(temIdx == desIdx && isTwo){
return (nums1[mIdx] + nums1[++mIdx]) / 2.0;
}else if(temIdx == desIdx + 1 && isTwo){
return (median + nums1[mIdx]) / 2.0;
}
mIdx++;
}else if(nIdx < n && mIdx == m){//当数组num1已经遍历完，而数据nums2还有数据
if(temIdx == desIdx && !isTwo){
return nums2[nIdx];
}else if(temIdx == desIdx && isTwo){
return (nums2[nIdx] + nums2[++nIdx]) / 2.0;
}else if(temIdx == desIdx + 1 && isTwo){
return (median + nums2[nIdx]) / 2.0;
}
nIdx++;
}
}
return median;
}
二、精简解法
用m表示第一个数组的长度，n表示第二个数组的长度，如果总长度为奇数，比如m=2，n=3，那么循环到(m+n)/2 + 1=(2+3)/2 + 1=3，也就是取第三个数，概括来说是第(m+n)/2 + 1个数。如果总长度为偶数，比如m=2，n=2，那么循环到(m+n)/2 + 1=(2+2)/2 + 1=3，取第2个和第3个数，概括来说是第(m+n)/2和(m+n)/2 + 1个数。使用两个变量pre和cur，pre表示上一次循环中找到的数，cur表示当前循环找到的数，每次在当前循环都把cur赋给pre，这样到最后一次找到的第(m+n)/2和(m+n)/2 + 1个数就是pre和cur，如果总长度为奇数直接取当前cur即可。
对于两个数组分别用mIdx和nIdx标示数组的下标，如果nums2数组此刻已经没有数字了，继续取数字 nums2[nIdx]，则会越界，所以判断nIdx是否大于数组长度，这样 || 后边的就不会执行了，也就不会导致错误了，所以增加为mIdx < m && (nIdx >= n || nums1[mIdx] < nums2[nIdx])。
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length,n = nums2.length;
int mIdx = 0, nIdx = 0;
//循环两个数组，按从小到大去获取，然后找到中间点的数，或者中间两个数，在寻找的过程中，pre记录上一个值，cur记录当前值。
int pre = 0, cur = 0;
//i从0到(m + n) / 2，当m + n为偶数时，i循环到中间两个数的后一个，当m + n为奇数时，i循环到中间那个数
for(int i = 0; i < (m + n) / 2 + 1; i++){
pre = cur;
if(mIdx < m && (nIdx >= n || nums1[mIdx] < nums2[nIdx])){
cur = nums1[mIdx++];
}else{
cur = nums2[nIdx++];
}
}
//两个数的时候，取pre和cur的平均
if((m + n) % 2 == 0){
return (pre + cur) / 2.0;
}else{//否则返回cur
return cur;
}
}
三、二分查找解法
根据中位数的定义，当m+n是奇数时，中位数是两个有序数组中的第(m+n)/2+1个元素，当m+n是偶数时，中位数是两个有序数组中的第(m+n)/2个元素和第(m+n)/2+1个元素的平均值。因此，这道题可以转化成寻找两个有序数组中的第k小的数，其中k为(m+n)/2或(m+n)/2+1。
假设两个有序数组分别是 A 和 B。要找到第 k 个元素，我们可以比较 A[k/2−1] 和 B[k/2−1]，其中/表示整数除法。由于A[k/2−1] 和B[k/2−1] 的前面分别有 A[0...k/2−2]和 B[0...k/2−2]，即 k/2−1 个元素，对于 A[k/2−1]和 B[k/2−1]中的较小值，最多只会有(k/2-1)+(k/2-1) = k−2个元素比它小，那么它就不能是第 k 小的数了。
有以下三种情况需要特殊处理：
- 如果
A[k/2−1]或者B[k/2−1]越界，那么我们可以选取对应数组中的最后一个元素。在这种情况下，我们必须根据排除数的个数减少k的值，而不能直接将k减去k/2-1。 - 如果一个数组为空，说明该数组中的所有元素都被排除，我们可以直接返回另一个数组中第 k 小的元素。
- 如果k=1，我们只要返回两个数组首元素的最小值即可。
主要思路：要找到第 k(k>1) 小的元素，那么就取 A[k/2-1] 和 B[k/2-1]进行比较。A 中小于等于 A[k/2-1]的元素有 A[0 .. k/2-2]共计 k/2-1个，B 中小于等于 B[k/2-1]的元素有B[0 .. k/2-2]共计k/2-1个。取 min(A[k/2-1], B[k/2-1])，两个数组中小于等于 min(A[k/2-1], B[k/2-1])的元素共计不会超过 (k/2-1) + (k/2-1) = k-2个，这样 min(A[k/2-1], B[k/2-1]) 本身最大也只能是第 k-1 小的元素。 如果 A[k/2-1] <= B[k/2-1]，那么 A[0 ... k/2-1]都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 A 数组；如果 A[k/2-1] > B[k/2-1]，那么 B[0 ... k/2-1]都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 B 数组。由于我们 "删除" 了一些元素(这些元素都比第 k 小的元素要小)，因此需要修改 k 的值，减去删除的数的个数(k/2-1)。"删除"是在indxA和indxB为基线，比如A[0 ... k/2-1]就是A[indxA ... indxA + k/2-1],B[0 ... k/2-1]就是B[indxB ... indxB + k/2-1]，删除时更新indxA和indxB即可。
//3.采用二分查找
//时间复杂度: O(log(m+n)), 空间复杂度: O(1)
public double findMedianSortedArrays(int[] A, int[] B) {
int lenA = A.length, lenB = B.length;
int len = lenA + lenB;
//如果是中间一个数为中位数
if (len % 2 == 1) {
//比如lenA = 2，lenB = 3，一共5个数那就取第3个数，也就是(lenA + lenB) / 2 + 1
int midIndx = len / 2 + 1;
return getKthElement(A, B, midIndx);
} else {
//如果是中间两个数为中位数，比如lenA = 2，lenB = 2，一共四个数，那就取第2个和第3个，也就是(lenA + lenB) / 2 和 (lenA + lenB) / 2 + 1
int midIndx= len / 2, midIndx2 = len / 2 + 1;
return (getKthElement(A, B, midIndx) + getKthElement(A, B, midIndx2)) / 2.0;
}
}
/** 主要思路：要找到第 k(k>1) 小的元素，那么就取 A[k/2-1] 和 B[k/2-1] 进行比较
* A 中小于等于 A[k/2-1] 的元素有 A[0 .. k/2-2] 共计 k/2-1 个
* B 中小于等于 B[k/2-1] 的元素有 B[0 .. k/2-2] 共计 k/2-1 个
* 取 min(A[k/2-1], B[k/2-1])，两个数组中小于等于 min(A[k/2-1], B[k/2-1]) 的元素共计不会超过 (k/2-1) + (k/2-1) = k-2 个
* 这样 min(A[k/2-1], B[k/2-1]) 本身最大也只能是第 k-1 小的元素
* 如果 A[k/2-1] <= B[k/2-1]，那么 A[0 ... k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 A 数组
* 如果 A[k/2-1] > B[k/2-1]，那么 B[0 ... k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 B 数组
* 由于我们 "删除" 了一些元素(这些元素都比第 k 小的元素要小)，因此需要修改 k 的值，减去删除的数的个数
* "删除"是在indxA和indxB为基线，比如A[0 ... k/2-1]就是A[indxA ... indxA + k/2-1], B[0 ... k/2-1]就是B[indxB ... indxB + k/2-1]，删除时更新indxA和indxB即可
*/
public int getKthElement(int[] A, int[] B, int k) {
int lenA = A.length, lenB = B.length;
int indxA = 0, indxB = 0;
while (true) {
//当A已经完全排除了，那就直接返回B中第k个元素的值
//这个第k个元素是在indxB的基础之上的偏移量，即B[indxB,...,indxB+(k-1),...]
if (indxA == lenA ) {
return B[indxB + (k - 1)];
}else if (indxB == lenB) {//当B已经完全排除了，那就直接返回A中第k个元素的值
return A[indxA + (k - 1)];
}else if (k == 1) {//如果现在要返回第一个元素，即k=1，那么就返回A和B第一个元素中最小的那个就好
return Math.min(A[indxA], B[indxB]);
}
//在数组A中，选择从indxA开始算起，第 k/2 个元素或者数组的最后一个，也就是当前数组A中要与B比较的那个元素的下标，这也是为了防止下标越界
int tempIndxA = Math.min(indxA + k / 2 - 1, lenA - 1);
//在数组B中，选择从indxB开始算起，第k / 2个元素或者数组的最后一个，也就是当前数组B中要与A比较的那个元素的下标
int tempIndxB = Math.min(indxB + k / 2 - 1, lenB - 1);
//如果A[tempIndxA] 小于等于 B[tempIndxB]，则排除A[indxA,...,tempIndxA]=tempIndxA - indxA + 1个元素
if (A[tempIndxA] <= B[tempIndxB]) {
k = k - (tempIndxA - indxA + 1);//目前是要找第k个元素，排除了tempIndxA - indxA + 1个，所以k要减去相应数量
indxA = tempIndxA + 1;//indxA指向后面一个元素，因为前面A[indxA,...,tempIndxA]个元素都排除了
} else {
k = k - (tempIndxB - indxB + 1);
indxB = tempIndxB + 1;
}
}
}
四、划分数组解法
中位数的定义：将一个集合划分为两个长度相等的子集，其中一个子集中的元素总是大于另一个子集中的元素。
首先，在任意位置 i 将A 划分成两个部分：
left_A | right_A
A[0], A[1], ..., A[i-1] | A[i], A[i+1], ..., A[m-1]
由于 A 中有 m 个元素， 所以有 m+1 种划分的方法(i∈[0,m])。
len(left_A)=i,len(right_A)=m−i.
注意：当 i = 0时，left_A 为空集， 而当 i = m 时, right_A 为空集。
采用同样的方式，在任意位置 j 将 B 划分成两个部分：
left_B | right_B
B[0], B[1], ..., B[j-1] | B[j], B[j+1], ..., B[n-1]
将left_A 和 left_B 放入一个集合，并将right_A 和right_B放入另一个集合。 再把这两个新的集合分别命名为 left_part 和 right_part：
left_part | right_part
A[0], A[1], ..., A[i-1] | A[i], A[i+1], ..., A[m-1]
B[0], B[1], ..., B[j-1] | B[j], B[j+1], ..., B[n-1]
当 A 和 B 的总长度是偶数时，如果可以确认：
- len(left_part)=len(right_part)
- max(left_part)≤min(right_part)
那么，{A,B} 中的所有元素已经被划分为相同长度的两个部分，且前一部分中的元素总是小于或等于后一部分中的元素。中位数就是前一部分的最大值和后一部分的最小值的平均值：
median=(max(left_part)+min(right_part))/2
当 A 和 B 的总长度是奇数时，如果可以确认：
- en(left_part)=len(right_part)+1
- max(left_part)≤min(right_part)
那么，{A,B} 中的所有元素已经被划分为两个部分，前一部分比后一部分多一个元素，且前一部分中的元素总是小于或等于后一部分中的元素。中位数就是前一部分的最大值：
第一个条件对于总长度是偶数和奇数的情况有所不同，但是可以将两种情况合并。第二个条件对于总长度是偶数和奇数的情况是一样的。
要确保这两个条件，只需要保证：
i + j = m - i + n - j(当 m+n为偶数)或i + j = m - i + n - j + 1(当 m+n为奇数)。等号左侧为前一部分的元素个数，等号右侧为后一部分的元素个数。将 i 和 j 全部移到等号左侧，我们就可以得到 。这里的分数结果只保留整数部分。0≤i≤m，0≤j≤n。如果我们规定 A 的长度小于等于 B 的长度，即 m≤n。这样对于任意的i∈[0,m]，都有∈[0,n]，那么我们在 [0,m] 的范围内枚举 i 并得到 j ，就不需要额外的性质了。- 如果A 的长度较大，那么我们只要交换A 和 B 即可。
- 如果 m > n ，那么得出的 j有可能是负数。
B[j−1]≤A[i]以及A[i−1]≤B[j]，即前一部分的最大值小于等于后一部分的最小值。
为了简化分析，假设A[i−1],B[j−1],A[i],B[j]总是存在。对于i=0、i=m、j=0、j=n这样的临界条件，我们只需要规定 A[−1]=B[−1]=−∞，A[m]=B[n]=∞即可。这也是比较直观的：当一个数组不出现在前一部分时，对应的值为负无穷，就不会对前一部分的最大值产生影响；当一个数组不出现在后一部分时，对应的值为正无穷，就不会对后一部分的最小值产生影响。
所以我们需要做的是：
在 [0, m]中找到 i，使得：
B[j−1]≤A[i] 且 A[i−1]≤B[j]，其中 j = (m + n + 1)/2 - i
我们证明它等价于：
在 [0, m]中找到最大的 i，使得：
A[i−1]≤B[j]，其中j = (m + n + 1)/2 - i
这是因为：
- 当 i从0∼m 递增时，A[i−1] 递增，B[j] 递减，所以一定存在一个最大的 i满足
A[i−1]≤B[j]； - 如果 i是最大的，那么说明 i+1 不满足。将 i+1带入可以得到
A[i]>B[j−1]，也就是B[j−1]<A[i]，就和我们进行等价变换前 i 的性质一致了
因此我们可以对 i 在 [0, m] 的区间上进行二分搜索，找到最大的满足 A[i−1]≤B[j] 的 i 值，就得到了划分的方法。此时，划分前一部分元素中的最大值，以及划分后一部分元素中的最小值，才可能作为就是这两个数组的中位数。
注：取自LeeCode官方解题思路
//4.划分数组
//时间复杂度: O(logmin(m,n))), 空间复杂度: O(1)
public double findMedianSortedArrays(int[] A, int[] B) {
//保证lenA < lenB
if (A.length > B.length) {
return findMedianSortedArrays(B, A);
}
int m = A.length;
int n = B.length;
int left = 0, right = m;
// medianFront：前一部分的最大值
// medianBack：后一部分的最小值
int medianFront = 0, medianBack = 0;
while (left <= right) {
// 前一部分包含 A[0 .. i-1] 和 B[0 .. j-1]
// 后一部分包含 A[i .. m-1] 和 B[j .. n-1]
int i = (left + right) / 2;
int j = (m + n + 1) / 2 - i;
//A_i_1 表示 A[i-1]
int A_i_1 = (i == 0 ? Integer.MIN_VALUE : A[i - 1]);
//A_i 表示 A[i]
int A_i = (i == m ? Integer.MAX_VALUE : A[i]);
//B_j_1 表示 B[j-1]
int B_j_1 = (j == 0 ? Integer.MIN_VALUE : B[j - 1]);
//B_j 表示 B[j]
int B_j = (j == n ? Integer.MAX_VALUE : B[j]);
//A[i-1] <= B[j]
if (A_i_1 <= B_j) {
medianFront = Math.max(A_i_1, B_j_1);//取前半部分的最大值
medianBack = Math.min(A_i, B_j);//取后半部分的最小值
left = i + 1;//剔除A[left,...,i]的部分，i去取A[left+1,...,right]
}else{
right = i - 1;//剔除A[i,...,right]的部分，i去取A[left,...,i-1]
}
}
return (m + n) % 2 == 0 ? (medianFront + medianBack) / 2.0 : medianFront;
}