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)).
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
分析 原文链接
该问题难在于，我们首先会考虑到对奇偶序列分开讨论，但实际上，这两种情况是可以合并的。
偶数序列中位数计算是这样的：
[2 3 5 7]则[2 3 / 5 7]
奇数序列中位数是这样的：
[2 3 4 5 6 7]则[2 3 (4/4) 5 6 7]
使用 L 代表左边序列的最大值，R 代表右边序列的最小值，则中位数就是 (L+R)/2
下面观察 L 和 R 随着 序列长度N的变化，产生的规律
N Index of L / R1 0 / 02 0 / 13 1 / 14 1 / 25 2 / 26 2 / 37 3 / 38 3 / 4
不难看出，L = ( N -1 ) / 2，R = N / 2。
所以中位数是：
(L + R)/2 = (A[(N-1)/2] + A[N/2])/2
下面，为了对两个序列的中位数问题求解，首先我们对序列进行一下预处理。
想象每个数字中间，都有一个 ‘#’ ，则序列的表示如下：
[6 9 13 18] -> [# 6 # 9 # 13 # 18 #] (N = 4) 偶数序列position index 0 1 2 3 4 5 6 7 8 (N_Position = 9)[6 9 11 13 18]-> [# 6 # 9 # 11 # 13 # 18 #] (N = 5) 奇数序列position index 0 1 2 3 4 5 6 7 8 9 10 (N_Position = 11)
可以看到，无论原来的序列是奇数还是偶数，经过处理的序列，总是 2N+1，是一个奇数序列。所以 分割线 '/' 位置总是在第N个（处理后的序列，以0为起始）。从而：
index ( L ) = ( N -1 ) / 2 = ( CutPosition - 1 ) / 2index ( R ) = N / 2 = CutPosition / 2;//CutPosition: 处理后序列的分割线位置
下面来看两组序列中位数的情况：
A1: [# 1 # 2 # 3 # 4 # 5 #] (N1 = 5, N1_positions = 11)A2: [# 1 # 1 # 1 # 1 #] (N2 = 4, N2_positions = 9)
和单序列求中位数情况类似，我们需要分割两个序列，使得其各自两部分，满足如下条件：
任意在 左半部分的数字 < 任意在 右半部分的数字
同时我们也可以做出如下推论：
1. A1 和 A2 两个序列总长度是 2*N1 + 2*N2 + 2。因此，分割以后，必须正好满足分割线左边部分位置个数为 N1 + N2，分割线右边位置个数也是 N1 + N2。两个分割线 ‘/' 占用 2 个位置。
2. 如果序列A2的分割线位置是C2 = k，那么A1的分割线位置C1应该满足 C1 = N1+N2 - k
3. 分割以后，会得到两个左半部分，两个右半部分，有如下关系：
L1 = A1[(C1-1)/2]; R1 = A1[C1/2];L2 = A2[(C2-1)/2]; R2 = A2[C2/2];
接下来就需要决定怎样确定分割线 ‘/’ 的位置了。 L1, L2 是左半边最大的数字，R1，R2是右半边最小的数字，我们必须保证
L1 <= R1 && L1 <= R2 && L2 <= R1 && L2 <= R2
因为L1 <= R1 和 L2 <= R2 是排序后数列自己保证的，所以我们简化条件为：
L1 <= R2 && L2 <= R1
接下来我们就可以通过简单的 二分查找 binary search 找到结果了。
1. 如果有L1 > R2，则说明A1序列左半边有太多过大的数字，所以 我们需要将C1左移（或者C2右移）2. 如果 L2 > R1，则说明A2序列左边有太多过大的数字，所以应该将C2左移（或者C1右移）3. 如果都没有，那么说明该 分割线位置是正确的4. 中位数medium就是 (max(L1,L2) + min(R1,R2)) / 2;
有两点需要注意：
1. C1和C2可以互相决定，所以我们可以选择短一些的序列进行查找，从而使得算法时间复杂度为log（min(N1,N2)）2. 唯一的边界条件edge case是当分割线落在 0 和 2N 的位置上。比如：如果C2 = 2*N2，那么R2 = A2[ 2*N2 / 2] = A2[ N2 ]，会越过边界。为了解决这个问题，我们可以这样处理：当 L 落到左边界，则令 L = INT_MIN, 当 R落到 右边界，则让R = INT_MAX
下面就是代码：
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 | class Solution {public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int N1 = nums1.size(); int N2 = nums2.size(); if (N1 < N2) return findMedianSortedArrays(nums2, nums1); if (N2 == 0) return (nums1[(N1 - 1) / 2] + nums1[N1 / 2]) / 2; int lo = 0, hi = 2 * N2; while (lo <= hi) { int cut2 = (lo + hi) / 2; int cut1 = N1 + N2 - cut2; double L1 = (cut1 == 0 ? INT_MIN : nums1[(cut1 - 1) / 2]); double R1 = (cut1 == 2*N1 ? INT_MAX : nums1[cut1 / 2]); double L2 = (cut2 == 0 ? INT_MIN : nums2[(cut2 - 1) / 2]); double R2 = (cut2 == 2*N2 ? INT_MAX : nums2[cut2 / 2]); if (L1 > R2) lo = cut2 + 1; else if (L2 > R1) hi = cut2 - 1; else return (max(L1, L2) + min(R1, R2)) / 2; } return -1; }}; |
使用类似的思想写出寻找 第K个元素的算法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | int findKth(vector<int>& nums1, vector<int>& nums2, int k) { int N1 = nums1.size(); int N2 = nums2.size(); if (N2 > N1) return findKth(nums2, nums1, k); if (N2 == 0) return nums1[min(k - 1, N1 - 1)];//防止k越界 int lo = 1, hi = N2; while (lo <= hi) { int cut2 = min((lo + hi) / 2, k ); int cut1 = min(k - cut2, N1);//当k大于两数列和时候，需要 int L1 = cut1 == 0 ? INT_MIN : nums1[cut1 - 1]; int R1 = cut1 == min(k, N1) ? INT_MAX : nums1[cut1]; int L2 = cut2 == 0 ? INT_MIN : nums2[cut2 - 1]; int R2 = cut2 == min(k, N2) ? INT_MAX : nums2[cut2]; if (L1 > R2) lo = cut2 + 1; else if (L2 > R1) hi = cut2 - 1; else return max(L1, L2); } return -1; } |
该算法可以找出当 k >2 时的双序列的第k个元素