-
算法—4、寻找两个正序数组的中位数
题目
给定两个大小分别为
m和n的正序(从小到大)数组nums1和nums2，找出并返回这两个正序数组的 中位数
算法的时间复杂度应该为o(log(m+n));
示例1输入： nums1 = [1,3], nums = [2] 输出： 2.0000 解释： 合并数组 = [1,2,3],中位数 2- 1
- 2
- 3
示例2
输入：nums1 = [1,2] 输出： 2.50000 解释： 合并数组 = [1,2,3,4]，中位数（2+3）/ 2 = 2.5- 1
- 2
- 3
思路
方法一：二分查找
给定两个有序数组，要求找到两个有序数组的中位数，最直观的思路有以下两种：- 使用归并的方式，合并两个有序数组，得到一个大的有序数组。大的有序数组的中间位置的元素，即为中位数。
- 不需要合并两个有序数组，只要找到中位数的位置即可。由于两个数组的长度已知，因此中位数对应的两个数组的下标之和也是已知的。维护两个指针，初始时分别指向两个数组的下标0的位置，每次将指向较小值的指针后移一位(如果一个指针已经达到数组末尾，则只需要移动另一个数组的指针，直到到达中位数的位置)
假设两个有序数组的长度分别为m和n，上述两种思路的复杂度如何？
第一种思路的时间复杂度是O(m+n)，空间复杂度是O(m+n).第二种思路虽然可以把空间复杂度降到O(1),但是时间复杂度仍是O(m+n)
如何把时间复杂度降低到O(log(m+n))呢？如果对时间复杂度的要求有log，通常都需要用到二分查找，这道题也可以通过二分查找实现。
根据中位数的定义，当m+n是奇数时，中位数是两个有序数组中的第(m+n)/2个元素，当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]，则A[k/2-1]小的数最多只有A的前k/2-1个数和B的前k/2-1个数，即比A[k/2-1]小的数最多只有k-2个，因此A[k/2-1]不可能是第k个数，A[0]到A[k/2-1]也都不可能是第k个数，可以全部排除。
- 如果A[k/2-1]>B[k/2-1],则可以排除B[0]到B[k/2-1]
- 如果A[kk/2-1]=B[k/2-1]，则可以归入第一种情况处理
可以看到，比较A[k/2-1]和B[k/2-1]之后，可以排除k/2个不可能是第k小的数，查找范围缩小了一半。同时，将在排除后的新数组上继续进行二分查找，并且根据排除的个数，减少k的值，这是因为排除的数都不大于第k小的数。
有以下三种情况需要特殊处理：- 如果A[k/2-1]或者B[k/2-1]越界，那么可以选取对应数组中的最后一个元素。在这种抢矿下，必须 根据排除数的个数减少k的值，而不能直接将k减去k/2.
- 如果一个数据为空，说明该数组中的所有元素都被排除，可以直接返回另一个数组中第k小的元素
- 如果k=1，只要返回两个数组首元素的最小值即可。
用一个例子说明上述算法。假设两个有序数组如下
A ：1 3 4 9 B:：1 2 3 4 5 6 7 8 9- 1
- 2
两个有序数组中下标为k/2-1=2的数，即A[2]和B[2],如下图所示：
A ：1 3 4 9 ^ B:：1 2 3 4 5 6 7 8 9 ^- 1
- 2
- 3
- 4
由于A[2]>B[3],因此排除B[0]到B[2],则数组B的下标偏移(offset)变为3，同时更新k的值：k=k-k/2=4.
下一步寻找，比较两个有序数组中下标为k/2-1=1的数，及A[1]到B[4],如下图所示，其中方括号部分标识已经被排除的数。A ：1 3 4 9 ^ B:：[1 2 3] 4 5 6 7 8 9 ^- 1
- 2
- 3
- 4
由于A[1]<B[4]，因此排除A[0]到A[1]，即数组A的下标偏移变为2，同步更新k的值：k= k-k/2=2.
下一步寻找，比较两个有序数组中下标为k/2-1=0的数，即比较A[2]和B[3]，如下图所示，其中方括号部分表示已经被排除的数：A ：[1 3] 4 9 ^ B:：[1 2 3] 4 5 6 7 8 9 ^- 1
- 2
- 3
- 4
由于A[2]=B[3]，根据之前的规则，排除A中的元素，因此排除A[2],即数组A的下标偏移变为3，同时更新k的值：k = k-k/2=1.
由于k的值变成1，因此比较两个有序数组中的未排除下标范围的第一个数，其中较小的数即为第k个数，由于A[3]>B[3]，因此第k个数是B[3]=4.class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int length1 = nums1.length, length2 = nums2.length; int totalLength = length1 + length2; if (totalLength % 2 == 1) { int midIndex = totalLength / 2; double median = getKthElement(nums1, nums2, midIndex + 1); return median; } else { int midIndex1 = totalLength / 2 - 1, midIndex2 = totalLength / 2; double median = (getKthElement(nums1, nums2, midIndex1 + 1) + getKthElement(nums1, nums2, midIndex2 + 1)) / 2.0; return median; } } public int getKthElement(int[] nums1, int[] nums2, int k) { /* 主要思路：要找到第 k (k>1) 小的元素，那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较 * 这里的 "/" 表示整除 * nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个 * nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个 * 取 pivot = min(pivot1, pivot2)，两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) <= k-2 个 * 这样 pivot 本身最大也只能是第 k-1 小的元素 * 如果 pivot = pivot1，那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums1 数组 * 如果 pivot = pivot2，那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums2 数组 * 由于我们 "删除" 了一些元素（这些元素都比第 k 小的元素要小），因此需要修改 k 的值，减去删除的数的个数 */ int length1 = nums1.length, length2 = nums2.length; int index1 = 0, index2 = 0; int kthElement = 0; while (true) { // 边界情况 if (index1 == length1) { return nums2[index2 + k - 1]; } if (index2 == length2) { return nums1[index1 + k - 1]; } if (k == 1) { return Math.min(nums1[index1], nums2[index2]); } // 正常情况 int half = k / 2; int newIndex1 = Math.min(index1 + half, length1) - 1; int newIndex2 = Math.min(index2 + half, length2) - 1; int pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2]; if (pivot1 <= pivot2) { k -= (newIndex1 - index1 + 1); index1 = newIndex1 + 1; } else { k -= (newIndex2 - index2 + 1); index2 = newIndex2 + 1; } } } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
复杂度分析
- 时间复杂度：O(log(m+n))，其中m和n分别是数组nums1和nums2的长度。初始时有k=(m+n)/2或k=(m+n)/2+1，每一轮循环可以将查找范围减少一半，因此时间复杂度是O(log(m+n))
- 空间复杂度：O(1)
方法二：划分数组
为了使用划分的方法解决这个问题，需要理解「中位数的作用是什么」。在统计中，中位数被用来将一个集合划分为两个长度相等的子集，其中一个子集中中的元素总是大于另一个子集中的元素
理解了中位数的划分作用，就很接近答案了。
首先，在任意位置，将A划分成两个部分：left_A | right_A A[0]，A[1]，...，A[i-1] | A[1]，A[i+1]，...，A[m-1]- 1
- 2
由于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 A[0]，A[1]，...，A[i-1] | A[1]，A[i+1]，...，A[m-1]- 1
- 2
将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] | A[j]，B[j+1]，...，B[n-1]- 1
- 2
- 3
当A和B的总长度是偶数时，如果可以确认：
- len(left_part) = len(right_part)
- max(left_part)<=min(right_part)
那么，[A,B]中的所有元素已经被划分为相同长度的两个部分，且前一部分中的元素总是小于或等于后一部分中的元素。中位数就是前一部分的最大值和后一部分的最小值的平均值：
当A和B的总长度是奇数时，如果可以确认：- len(left_part)=len(right_part)=1
- max(left_part)<=max(right_part)
那么，{A,B}中的所有元素都已经被划分为两个部分，前一部分比后一部分多一个元素，且前一部分的元素总是小于或等于后一部分中的元素。中位数就是前一部分的最大值：
median= max(left_part)
第一个条件对于总长度是偶数和奇数的情况有所不同，但是可以将两种情况合并，。第二个条件对于总长度是偶数和奇数的情况是一样的。
要确保这两个条件，只需要保证：- i+j=m-i=n-j（当m+n为偶数）或i+j=m-i=n-j+1（当m+n为奇数）。等号左侧为前一部分的元素个数，等号右侧为后一部分的元素个数。将i和j全部移到等号左侧，就可以得到i+j=(m+n+1)/2。这里的分数只保留整数部分
- 0<=i<=m,0<=j<=n.如果规定A的长度小于等于B的长度，即m<=n。这样对于任意的t∈[0nm],都有j=(m+n+1)/2-i∈[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值，就得到了划分的方法。此时，划分前一部分元素中的最大值，以及划分后一部分元素中的最小值，才可能作为这两个数组的中位数。
class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { if (nums1.length > nums2.length) { return findMedianSortedArrays(nums2, nums1); } int m = nums1.length; int n = nums2.length; int left = 0, right = m; // median1：前一部分的最大值 // median2：后一部分的最小值 int median1 = 0, median2 = 0; while (left <= right) { // 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1] // 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1] int i = (left + right) / 2; int j = (m + n + 1) / 2 - i; // nums_im1, nums_i, nums_jm1, nums_j 分别表示 nums1[i-1], nums1[i], nums2[j-1], nums2[j] int nums_im1 = (i == 0 ? Integer.MIN_VALUE : nums1[i - 1]); int nums_i = (i == m ? Integer.MAX_VALUE : nums1[i]); int nums_jm1 = (j == 0 ? Integer.MIN_VALUE : nums2[j - 1]); int nums_j = (j == n ? Integer.MAX_VALUE : nums2[j]); if (nums_im1 <= nums_j) { median1 = Math.max(nums_im1, nums_jm1); median2 = Math.min(nums_i, nums_j); left = i + 1; } else { right = i - 1; } } return (m + n) % 2 == 0 ? (median1 + median2) / 2.0 : median1; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
复杂度分析
- 时间复杂度：O(log min(m,n))，其中m和n分别是数组nums1和nums2的长度。查找的区间是[0,m]，而该区间的长度在每次循环之后都会较少为原来的一半。所以，只需要执行log m次循环。由于每次循环中的操作次数是常数，所以时间复杂度为O(log m)。由于可能需要交换nums1和nums2使得m<=n，因此时间复杂度是O(log min(m,n))
- 空间复杂度： O(1)
练习代码
public class Test_5 { public static double findMedianSortedArrays(int[] nums1, int[] nums2) { int len1 = nums1.length,len2 = nums2.length; int totalLen = len1+len2; if (totalLen%2==1){ int midIndex = totalLen/2; double midian = getKthElement(nums1,nums2,midIndex+1); return midian; }else { int midIndex1 = totalLen/2-1,midIndex2 = totalLen/2; double midian = (getKthElement(nums1,nums2,midIndex1+1)+getKthElement(nums1,nums2,midIndex2+1))/2.0; return midian; } } private static int getKthElement(int[] nums1, int[] nums2, int k) { int len1 = nums1.length,len2 = nums2.length; int index1=0,index2=0; int kthElement = 0; while (true){ if (index1==len1){ return nums2[index2+k-1]; } if (index2==len2){ return nums1[index1+k-1]; } if (k==1){ return Math.min(nums1[index1],nums2[index2]); } int half = k/2; int newIndex1 = Math.min(index1+half,len1)-1; int newIndex2 = Math.min(index2+half,len2)-1; int pivot1 = nums1[newIndex1],pivot2 = nums2[newIndex2]; if (pivot1<=pivot2){ k-=(newIndex1-index1)+1; index1 = newIndex1+1; }else { k-=(newIndex2-index2)+1; index2 = newIndex2+1; } } } public static void main(String[] args) { int[] num1 = new int[4]; int[] num2 = new int[9]; num1[0]=1; num1[1]=3; num1[2]=4; num1[3]=9; num2[0]=1; num2[1]=2; num2[2]=3; num2[3]=4; num2[4]=5; num2[5]=6; num2[6]=7; num2[7]=8; num2[8]=9; int[] num3 = new int[2]; int[] num4 = new int[2]; num3[0]=0; num3[1]=0; num4[0]=0; num4[1]=0; System.out.println(findMedianSortedArrays(num3,num4)); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
-
相关阅读:
园子开店记-起名：万事开头难，起名难上难
信号与进程间通信
Oracle （7）Online Redo Log Files
haproxy
javaWeb项目-房屋房租租赁系统功能介绍
CSS @property，让不可能变可能
从代码入手理解卡尔曼滤波器的原理之使用Eigen实现二维卡尔曼滤波器（七）
模型部署 利用Tensorflow Serving部署模型
网页计算器
提升吃鸡战斗力，分享顶级作战干货！
- 原文地址：https://blog.csdn.net/qq_32530561/article/details/125594062
