/*
算法思想:
空间复杂度:O(1), 时间复杂度:O(m+n)
*/
// 查找两个有序序列中的中位数
int find_mid(int s1[], int s2[], int m, int n) {
if (m + n == 0) return;
int mid = (m + n) / 2; // 计算中间的元素的下标
else if (m + n % 2 == 1) return find_k(mid); // 奇数返回正中间的数
else return ( find_k(mid - 1) + find_k(mid) ) / 2; // 偶数返回中间两数的平均数
}
// 查找两个有序序列中第k个元素
int find_k(int s1[], int s2[], int m, int n, int k) {
if ( k >= m + n) return -1;
int i = 0, j = 0;
int target = -1, cnt = 0;
while(i < m && j < n) {
if (s1[i] < s2[j]) {
target = s1[i];
i ++;
}
else {
target = s2[j];
j ++;
}
if (++ cnt == k) break;
}
if (i < m && cnt != k) {
i = k - n - 1;
target = s1[i];
}
if (j < m && cnt != k) {
j = k - m - 1;
target = s2[j];
}
return target;
}
/*
算法思想:
空间复杂度:O(1), 时间复杂度:O(n)
*/
int find_mid(int s1[], int s2[], int m, int n) {
if (m + n == 0) return;
int mid = (m + n) / 2; // 计算中间的元素的下标
else if (m + n % 2 == 1) return find_k(mid); // 奇数返回正中间的数
else return ( find_k(mid - 1) + find_k(mid) ) / 2; // 偶数返回中间两数的平均数
}
// 查找两个有序序列中第k个元素
int find_k(int s1[], int s2[], int m, int n, int k) {
if ( k >= m + n) return -1;
int i = 0, j = 0;
int target = -1, cnt = 0;
while(i < m && j < n) {
if (s1[i] < s2[j])
target = s1[i ++];
else target = s2[j ++];
if (++ cnt == k) break;
}
if (i < m && cnt != k)
target = s1[k - n - 1];
if (j < m && cnt != k)
target = s2[k - m - 1];
return target;
}