vlambda博客
学习文章列表

 二分查找系列专题   第四篇

给定两个有序数组arr1和arr2，已知两个数组的⻓度分别为 m1 和 m2，求两个数组中的第 K ⼩数。要求时间复杂度O(log(m1 + m2))。

举例

arr1 = [1,2,3]，arr2 = [3,4,5,6]，K = 4。
则第 K ⼩数为 3.

arr1 = [0,1,2]，arr2 = [3,4,5,7,8]， K = 3;
则第 K ⼩数为 2.

题解

本题仍然要求对数时间复杂度，因此也是要使用二分法的，思路和类似。思路：利用二分的思路，每次移动两个数组中左边的指针，把求两个数组的第 小元素不断转化为求解第 小元素，如此缩小范围。

下面给出图解：

int findKth(vector<int>& vec1, int l1, int r1, vector<int>& vec2, int l2, int r2, int k) {
    if (l1 > r1) return vec2[l2 + k];
    if (l2 > r2) return vec1[l1 + k];
    if (k == 0) return min(vec1[l1], vec2[l2]);
    int mid1 = l1 + k / 2 < r1 ? l1 + k / 2 : r1;
    int mid2 = l2 + k / 2 < r2 ? l2 + k / 2 : r2;
    if (vec1[mid1] <= vec2[mid2]) {
        return findKth(vec1, mid1 + 1, r1, vec2, l2, r2, k - k / 2 - 1);
    }
    else {
	return findKth(vec1, l1, r1, vec2, mid2 + 1, r2, k - k / 2 - 1);
    }
}

int getKthMin(vector<int>& vec1, vector<int>& vec2, int k) {
    int len1 = vec1.size();
    int len2 = vec2.size();
    if (len1 == 0) return vec2[k - 1];
    if (len2 == 0) return vec1[k - 1];
    return findKth(vec1, 0, len1 - 1, vec2, 0, len2 - 1, k - 1);
}