寻找两个正序数组的中位数
原创寻找两个正序数组的中位数
原创
PHP开发工程师
发布于 2022-04-18 14:21:24
发布于 2022-04-18 14:21:24
题目描述
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
思路分析
几种比较好想的方式，已知数组有序，所以我们可以像合并链表时逐个合并的方式进行依次遍历，直到遍历到中位数。
时间复杂度是O(n)，空间复杂度为O(1)，只需要维护两个指针即可。
也可以使用堆，将元素全部填入堆中，并逐个弹出，并不是一个好办法，因为没有节省时间复杂度的同时，增加了空间复杂度。
我们看到数组本身有序，那么是否可以在数组有序的前提下，使用更优解呢？
顺着这个思路我们想到二分，我们假设数组A有n个元素，B也有n个元素，当数组有序时，中位数为合并数组的第n个和第n+1个位置的平均数。
我门虽然不知道前n+1在数组A、B的分布情况，但我们也知道，一定在前n+1个元素中，在此基础上，比较A，B数组一半位置的值。
如果
arrA[n / 2 - 1] > arrB[n / 2 - 1] 则说明比arrB[n / 2 - 1]小的数的数量一定小于n，因此可以排除一部分范围，不断缩小范围，即可得到答案
关键代码如下
while (true) {
// 边界情况
if (index1 == m) {
return nums2[index2 + k - 1];
}
if (index2 == n) {
return nums1[index1 + k - 1];
}
if (k == 1) {
return min(nums1[index1], nums2[index2]);
}
// 正常情况
int newIndex1 = min(index1 + k / 2 - 1, m - 1);
int newIndex2 = min(index2 + k / 2 - 1, n - 1);
int pivot1 = nums1[newIndex1];
int pivot2 = nums2[newIndex2];
if (pivot1 <= pivot2) {
k -= newIndex1 - index1 + 1;
index1 = newIndex1 + 1;
}
else {
k -= newIndex2 - index2 + 1;
index2 = newIndex2 + 1;
}
}原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录