leetcode-寻找两个正序数组的第K大的数

两个正序数组(从小到大), 找到两个数组的所有元素里的第K大的数。

思路

对两个有序数组同时使用二分法,由于是K个,将问题转化为K为了数组的中位数,然后利用中位数的特性,若当前数不满足条件,就舍弃掉之前的所有的元素

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int FindkthNum(vector<int> nums1,int index1, vector<int> nums2, int index2, int K) {
if (index1 == nums1.size()) return nums2[index2 + K - 1];
if (index2 == nums2.size()) return nums1[index1 + K - 1];
if (K == 1) return min(nums1[index1], nums2[index2]);

//二分的中间值
//判断此时是否超出边界
int mid1 = ((index1 + K/2 - 1) < nums1.size()) ? nums1[index1 + K/2 - 1] : INT_MAX;
int mid2 = ((index2 + K/2 - 1) < nums2.size()) ? nums2[index2 + K/2 - 1] : INT_MAX;

//对比,然后舍弃掉中位数之前的数
if (mid1 < mid2)
return FindkthNum(nums1, index1+K/2, nums2, index2, K - K/2);
else
return FindkthNum(nums1, index1, nums2, index2 + K/2, K - K/2);
}
};

复杂度

时间:O(log(m+n)), 空间O(log(m+n))

作者

Dylan Zhu

发布于

2021-04-12

更新于

2021-04-15

许可协议

评论

:D 一言句子获取中...

加载中,最新评论有1分钟缓存...