两个有序数组分别是 A[0:n−1] 和 B[0:n−1] 。要找到第 n 个元素，我们可以比较 A[⌈n/2⌉−1] 和 B[⌈n/2⌉−1] 。
由于 A[⌈n/2⌉−1] 和 B[⌈n/2⌉−1] 的前面分别有 A[0:⌈n/2⌉−2] 和 B[0:⌈n/2⌉−2] ，即各有 ⌈n/2⌉−1 个元素，对于 min{A[⌈n/2⌉−1],B[⌈n/2⌉−1]} ，
若 n 为奇数，则 2(⌈n/2⌉−1)<2(n/2+1−1)=n ，最多只会有 n−1 个元素比它小，也就是 min{A[⌈n/2⌉−1],B[⌈n/2⌉−1]} 最多恰为第 n 小的数，这里先假设 A[⌈n/2⌉−1]<B[⌈n/2⌉−1] ，则 A[0:⌈n/2⌉−2] （等价于 A[0:⌊n/2⌋−1] ）都小于或等于 A[⌈n/2⌉−1] ，可以直接排除。
若 n 为偶数，则 2(⌈n/2⌉−1)=2(n/2−1)=n−2 ，最多只会有 n−2 个元素比它小，也就是 min{A[⌈n/2⌉−1],B[⌈n/2⌉−1]} 最多恰为第 n−1 小的数，这里先假设 A[⌈n/2⌉−1]<B[⌈n/2⌉−1] ，则 A[0:⌈n/2⌉−1] （等价于 A[0:⌊n/2⌋−1] ）都小于或等于 A[⌈n/2⌉−1] ，可以直接排除。
由于 A[⌈n/2⌉−1] 和 B[⌈n/2⌉−1] 的后面分别有 A[⌈n/2⌉:n−1] 和 B[⌈n/2⌉:n−1] ，即各有 n−⌈n/2⌉ 个元素，对于 max{A[⌈n/2⌉−1],B[⌈n/2⌉−1]} ，因为 2(n−⌈n/2⌉)≤2(n−n/2)=n 最多只会有 n 个元素比它大，也就是 max{A[⌈n/2⌉−1],B[⌈n/2⌉−1]} 最少恰为第 n 小的数，这里先假设 A[⌈n/2⌉−1]<B[⌈n/2⌉−1] ，则 B[⌈n/2⌉:n−1] （等价于 B[n−⌊n/2⌋−1:n−1] ）都大于或等于 B[⌈n/2⌉−1] ，可以直接排除。
因此我们可以归纳出三种情况：
- 情况一： A[⌈n/2⌉−1]<B[⌈n/2⌉−1] ，排除 A[0:⌊n/2⌋−1] 和 B[n−⌊n/2⌋−1:n−1] ，同时缩小 n 为 ⌈n/2⌉ 。
- 情况二： A[⌈n/2⌉−1]>B[⌈n/2⌉−1] ，排除 A[n−⌊n/2⌋−1:n−1] 和 B[0:⌊n/2⌋−1] ，同时缩小 n 为 ⌈n/2⌉ 。
- 情况三： A[⌈n/2⌉−1]=B[⌈n/2⌉−1] ，归纳为情况一或者情况二。
其实我们可以对情况三进行进一步讨论，此时设 A[⌈n/2⌉−1]=B[⌈n/2⌉−1]=m 。
若 n 为奇数，此时恰有 n−1 个元素小于或等于 m ，且恰有 n−1 个元素大于或等于 m ，取 A[⌈n/2⌉−1] 或 B[⌈n/2⌉−1] 放入大于或等于 m 的集合，则恰有 n−1 个元素小于或等于 m ，且恰有 n 个元素大于或等于 m ，则 m 为中位数，可以直接返回。
若 n 为偶数，此时恰有 n−2 个元素小于或等于 m ，且恰有 n−1 个元素大于或等于 m ，取 A[⌈n/2⌉−1] 或 B[⌈n/2⌉−1] 放入小于或等于 m 的集合，则恰有 n−1 个元素小于或等于 m ，且恰有 n 个元素大于或等于 m ，则 m 为中位数，可以直接返回。
因此三种情况可以优化为：
- 情况一： A[⌈n/2⌉−1]<B[⌈n/2⌉−1] ，排除 A[0:⌊n/2⌋−1] 和 B[n−⌊n/2⌋−1:n−1] ，同时缩小 n 为 ⌈n/2⌉ 。
- 情况二： A[⌈n/2⌉−1]>B[⌈n/2⌉−1] ，排除 A[n−⌊n/2⌋−1:n−1] 和 B[0:⌊n/2⌋−1] ，同时缩小 n 为 ⌈n/2⌉ 。
- 情况三： A[⌈n/2⌉−1]=B[⌈n/2⌉−1] ，直接返回 A[⌈n/2⌉−1] 。
递归调用上述过程，终止情况：
因为 0<⌈n/2⌉<n−1 ，所以不会越界。
画出有向图，→指向表示有向边，有向边起点元素小于或等于有向边终点元素。
如上图，灰色结点淘汰。
递归版本一，保存下标，为原地算法。这里总共有五个变量， 两个数组的首尾元素下标合计4个，数组长度一个，由于 p+n−1=r ，我们只记录 A 首个元素下标 pa ，B 首个元素下标 pb ，和数组长度 n 。
C代码如下（含测试用例）：
#include <stdio.h>
int min(int x, int y) {
return x < y ? x : y;
}
int findMedian(int *a, int *b, int n, int pa, int pb) {
if (n == 1) {
return min(a[pa], b[pb]);
}
int ma = pa + (n + 1) / 2 - 1;
int mb = pb + (n + 1) / 2 - 1;
if (a[ma] < b[mb]) {
return findMedian(a, b, (n + 1) / 2, pa + n / 2, pb);
} else if (a[ma] > b[mb]) {
return findMedian(a, b, (n + 1) / 2, pa, pb + n / 2);
} else {
return a[ma];
}
}
int findMedianSortedArrays(int *A, int *B, int n) {
return findMedian(A, B, n, 0, 0);
}
int main() {
int s1[] = {11, 13, 15, 17, 19};
int s2[] = {2, 4, 6, 8, 20};
printf("%d", findMedianSortedArrays(s1, s2, 5));
return 0;
}
C++代码如下（含测试用例）：
#include <iostream>
#include <vector>
using namespace std;
int findMedian(vector<int>& A, vector<int>& B, int pa, int pb, int n) {
if (n == 1) {
return min(A[pa], B[pb]);
}
int ma = pa + (n + 1) / 2 - 1;
int mb = pb + (n + 1) / 2 - 1;
if (A[ma] < B[mb]) {
return findMedian(A, B, pa + n / 2, pb, (n + 1) / 2);
} else if (A[ma] > B[mb]) {
return findMedian(A, B, pa, pb + n / 2, (n + 1) / 2);
} else {
return A[ma];
}
}
int findMedianSortedArrays(vector<int>& A, vector<int>& B) {
int n = (int)A.size();
return findMedian(A, B, 0, 0, n);
}
int main() {
vector<int>s1 = {11, 13, 15, 17, 19};
vector<int>s2 = {2, 4, 6, 8, 20};
cout << findMedianSortedArrays(s1, s2);
return 0;
}
- 时间复杂度： O(logn) 。
- 空间复杂度： O(1) 。
迭代版本一，保存下标，为原地算法。
C代码如下（含测试用例）：
#include <stdio.h>
int min(int x, int y) {
return x < y ? x : y;
}
int findMedianSortedArrays(int *a, int *b, int n) {
int pa = 0, pb = 0, ma, mb;
while (n > 1) {
ma = pa + (n + 1) / 2 - 1;
mb = pb + (n + 1) / 2 - 1;
if (a[ma] == b[mb]) return a[ma];
if (a[ma] < b[mb]) {
pa += n / 2;
} else {
pb += n / 2;
}
n = (n + 1) / 2;
}
return min(a[pa], b[pb]);
}
int main() {
int s1[] = {11, 13, 15, 17, 19};
int s2[] = {2, 4, 6, 8, 20};
printf("%d", findMedianSortedArrays(s1, s2, 5));
return 0;
}
C++代码如下（含测试用例）：
#include <iostream>
#include <vector>
using namespace std;
int findMedianSortedArrays(vector<int>& A, vector<int>& B) {
int n = (int)A.size();
int pa = 0, pb = 0, ma, mb;
while (n > 1) {
ma = pa + (n + 1) / 2 - 1;
mb = pb + (n + 1) / 2 - 1;
if (A[ma] == B[mb]) return A[ma];
if (A[ma] < B[mb]) {
pa += n / 2;
} else {
pb += n / 2;
}
n = (n + 1) / 2;
}
return min(A[pa], B[pb]);
}
int main() {
vector<int>s1 = {11, 13, 15, 17, 19};
vector<int>s2 = {2, 4, 6, 8, 20};
cout << findMedianSortedArrays(s1, s2);
return 0;
}
- 时间复杂度： O(logn) 。
- 空间复杂度： O(1) 。
迭代版本二，C代码如下（含测试用例）：
#include <stdio.h>
int min(int x, int y) {
return x < y ? x : y;
}
int findMedianSortedArrays(int *A, int *B, int n) { // n即为序列长度L
int s1 = 0, e1 = n - 1, mid1, s2 = 0, e2 = n - 1, mid2;
while(s1 != e1 || s2 != e2) {
mid1 = (s1 + e1) / 2;
mid2 = (s2 + e2) / 2;
if (A[mid1] == B[mid2]) {
return A[mid1];
} else if (A[mid1] < B[mid2]) {
// 分别考虑奇数和偶数，保持两个子数组元素个数相等
if ((s1 + e1) % 2 == 0) { // 若元素个数为奇数
s1 = mid1; // 舍弃A中间点以前的部分
e2 = mid2; // 舍弃B中间点以后的部分
} else { // 若元素个数为偶数
s1 = mid1 + 1; // 舍弃A中间点及中间点以前的部分
e2 = mid2; // 舍弃B中间点以后的部分
}
} else {
// 分别考虑奇数和偶数，保持两个子数组元素个数相等
if ((s1 + e1) % 2 == 0) { // 若元素个数为奇数
e1 = mid1; // 舍弃A中间点以后的部分
s2 = mid2; // 舍弃B中间点以前的部分
} else { // 若元素个数为偶数
e1 = mid1; // 舍弃A中间点以后的部分
s2 = mid2 + 1; // 舍弃B中间点及中间点以前的部分
}
}
}
return min(A[s1], B[s2]);
}
int main() {
int s1[] = {11, 13, 15, 17, 19};
int s2[] = {2, 4, 6, 8, 20};
printf("%d", findMedianSortedArrays(s1, s2, 5));
return 0;
}
C++代码如下（含测试用例）：
#include <iostream>
#include <vector>
using namespace std;
int findMedianSortedArrays(vector<int>& A, vector<int>& B) {
const int n = A.size();
int s1 = 0, e1 = n - 1, mid1, s2 = 0, e2 = n - 1, mid2;
while(s1 != e1 || s2 != e2) {
mid1 = (s1 + e1) / 2;
mid2 = (s2 + e2) / 2;
if (A[mid1] == B[mid2]) {
return A[mid1];
} else if (A[mid1] < B[mid2]) {
// 分别考虑奇数和偶数，保持两个子数组元素个数相等
if ((s1 + e1) % 2 == 0) { // 若元素个数为奇数
s1 = mid1; // 舍弃A中间点以前的部分
e2 = mid2; // 舍弃B中间点以后的部分
} else { // 若元素个数为偶数
s1 = mid1 + 1; // 舍弃A中间点及中间点以前的部分
e2 = mid2; // 舍弃B中间点以后的部分
}
} else {
// 分别考虑奇数和偶数，保持两个子数组元素个数相等
if ((s1 + e1) % 2 == 0) { // 若元素个数为奇数
e1 = mid1; // 舍弃A中间点以后的部分
s2 = mid2; // 舍弃B中间点以前的部分
} else { // 若元素个数为偶数
e1 = mid1; // 舍弃A中间点以后的部分
s2 = mid2 + 1; // 舍弃B中间点及中间点以前的部分
}
}
}
return min(A[s1], B[s2]);
}
int main() {
vector<int>s1 = {11, 13, 15, 17, 19};
vector<int>s2 = {2, 4, 6, 8, 20};
cout << findMedianSortedArrays(s1, s2);
return 0;
}
时间复杂度： O(logn) 。
空间复杂度： O(1) 。
，此时跳出循环时，解得 
。
次，所以该过程时间复杂度为 
。
，表示从 a 到 b 的所有整数，包括 a 和 b 。
，或者
。
，有四种写法：
，当 front=rear 时，显然有 
，即
。
，初始时队列为空，有
，推出 rear=front−1=0−1=−1 ，由于循环队列位置非负，将 −1 修改为 (−1+n)modn=n−1 即可。
。
或 ¬A 。
和 
，显然前者权值6小于后者4+5=9，所以关键路径包含 
。
和 
，显然前者权值4+3=7大于后者3+3=6，所以关键路径包含 
。
，即为关键路径，关键路径长度为 4+5+4+3=16 。
，其中 ACK = 1，SYN = 0。
The road of your choice, you have to go on !
粤ICP备16082171号-1
