给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。 算法的时间复杂度应该为 O(log (m+n)) 。 c语言
时间: 2024-05-25 18:17:48 浏览: 17
解法:二分查找
题目要求时间复杂度为 O(log(m+n)),可以考虑使用二分查找。
假设我们要在两个有序数组 nums1 和 nums2 中找到第 k 小的数,我们可以分别在 nums1 和 nums2 中查找第 k/2 小的数,设其为 mid1 和 mid2,比较这两个数的大小:
- 如果 mid1 小于 mid2,则说明 nums1 中的前 k/2 个数都不是第 k 小的数,因为这些数加起来也不到 k,所以我们可以将 nums1 中的前 k/2 个数全部排除。更新 k 的值,让 k 减去 nums1 中排除的数的个数,同时让 nums1 的起始位置向后移动 k/2 个位置。
- 如果 mid1 大于 mid2,则说明 nums2 中的前 k/2 个数都不是第 k 小的数,因为这些数加起来也不到 k,所以我们可以将 nums2 中的前 k/2 个数全部排除。更新 k 的值,让 k 减去 nums2 中排除的数的个数,同时让 nums2 的起始位置向后移动 k/2 个位置。
- 如果 mid1 等于 mid2,则说明找到了第 k 小的数,直接返回 mid1 或 mid2 即可。
注意边界情况:
- 当其中一个数组的起始位置超过数组长度,说明该数组已经全部排除,直接返回另一个数组的第 k 小的数。
- 如果 k=1,则两个数组中的最小值即为第一小的数,直接返回两个数组的起始位置指向的数中的最小值。
具体实现见下面的代码:
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
int totalSize = nums1Size + nums2Size;
if (totalSize % 2 == 1) { // 总数为奇数
return findKthSmallest(nums1, nums1Size, nums2, nums2Size, totalSize / 2 + 1);
} else { // 总数为偶数
return (findKthSmallest(nums1, nums1Size, nums2, nums2Size, totalSize / 2) +
findKthSmallest(nums1, nums1Size, nums2, nums2Size, totalSize / 2 + 1)) / 2.0;
}
}
// 在 nums1 和 nums2 中查找第 k 小的数
int findKthSmallest(int* nums1, int nums1Size, int* nums2, int nums2Size, int k) {
if (nums1Size > nums2Size) { // 保证 nums1 的长度不大于 nums2 的长度
return findKthSmallest(nums2, nums2Size, nums1, nums1Size, k);
}
if (nums1Size == 0) { // nums1 数组为空
return nums2[k - 1];
}
if (k == 1) { // 找第一小的数,即两个数组中的最小值
return fmin(nums1[0], nums2[0]);
}
int mid1 = fmin(nums1Size, k / 2); // 在 nums1 中查找第 k/2 小的数
int mid2 = k - mid1; // 在 nums2 中查找第 k-mid1 小的数
if (nums1[mid1 - 1] < nums2[mid2 - 1]) { // nums1 的前 mid1 个数都不是第 k 小的数
return findKthSmallest(nums1 + mid1, nums1Size - mid1, nums2, nums2Size, k - mid1);
} else if (nums1[mid1 - 1] > nums2[mid2 - 1]) { // nums2 的前 mid2 个数都不是第 k 小的数
return findKthSmallest(nums1, nums1Size, nums2 + mid2, nums2Size - mid2, k - mid2);
} else { // 找到了第 k 小的数
return nums1[mid1 - 1];
}
}
时间复杂度分析:每次查找时,我们都可以排除掉 k/2 个数,因此最多需要查找 log(k) 次,即时间复杂度为 O(log(k))。由于 k 最大为 m+n,因此时间复杂度为 O(log(m+n))。