算法的核心思想是利用二分搜索法来逐步缩小搜索范围,通过每次排除掉一部分不可能是第k小数的元素,从而高效地找到两个有序序列合并后的第k小的数。具体步骤如下:
-
二分逻辑:在每一步中,算法都试图在两个序列中各自找到第k/2小的元素。通过比较这两个元素的大小,可以确定较小的那个元素及其之前的所有元素都不可能是第k小的数(因为即使这些元素与另一个序列中所有较小的元素合并,其数量也达不到k)。因此,这些元素可以被安全排除。
-
更新k的值:排除掉一部分元素后,我们不再寻找原始的第k小的数,而是寻找更新后的第k - k/2小的数。这是因为我们已经排除了k/2个不可能的候选,相当于我们的目标在合并后的序列中向前移动了k/2的位置。
-
递归直到k=1:重复这个过程,每次递归都会减少k的值,直到k减小到1。此时,我们只需要比较两个序列当前考虑的第一个元素,较小的那个就是当前搜索范围内的最小元素,也就是合并后序列中的第k小的数。
-
处理边界情况:在实际操作中,还需要考虑一些边界情况,比如某个序列的长度小于k/2时,如何调整搜索策略,以及如何处理序列为空的情况。
通过这种方式,算法能够在O(log(m+n))的时间复杂度内找到答案,其中m和n分别是两个序列的长度。这种方法相比直接合并两个序列后再找第k小的数要高效得多,因为它避免了合并的O(m+n)时间复杂度和可能的O(m+n log(m+n))的排序时间复杂度。
#include<bits/stdc++.h>
using namespace std;
// 寻找两个有序数组中第k小的数
int findKth(vector<int>& nums1, int start1, vector<int>& nums2, int start2, int k)
{
// 边界情况:如果nums1的起始位置超过了其长度,说明nums1中的元素已经被排除完,
// 此时直接从nums2中取第k小的数
if (start1 >= nums1.size()) return nums2[start2 + k - 1];
// 同理,如果nums2的起始位置超过了其长度,说明nums2中的元素已经被排除完,
// 此时直接从nums1中取第k小的数
if (start2 >= nums2.size()) return nums1[start1 + k - 1];
// 如果k等于1,表示我们要找的是两个数组中的最小值,直接返回两个数组当前考虑的首元素中的较小者
if (k == 1) return min(nums1[start1], nums2[start2]);
// 比较两个数组中的第k/2个元素,但要注意数组长度可能不足k/2
// 如果数组长度不足k/2,则将比较值设为INT_MAX,确保不会被选中
int midVal1 = (start1 + k / 2 - 1 < nums1.size()) ? nums1[start1 + k / 2 - 1] : INT_MAX;
int midVal2 = (start2 + k / 2 - 1 < nums2.size()) ? nums2[start2 + k / 2 - 1] : INT_MAX;
// 根据两个数组的第k/2个元素的比较结果,决定下一步递归的方向
// 如果nums1的中间值较小,说明nums1中的这k/2个元素都不是第k小的数,
// 可以排除,将nums1的起始位置向前移动k/2个位置
if (midVal1 < midVal2)
{
return findKth(nums1, start1 + k / 2, nums2, start2, k - k / 2);
}
else
{
// 同理,如果nums2的中间值较小,排除nums2中的这k/2个元素,
// 将nums2的起始位置向前移动k/2个位置
return findKth(nums1, start1, nums2, start2 + k / 2, k - k / 2);
}
}
int main()
{
vector<int> nums1 = {1, 3, 5, 7, 9, 11};
vector<int> nums2 = {2, 4, 6, 8, 10};
int k = 6;
cout << findKth(nums1, 0, nums2, 0, k);
return 0;
}