寻找两个正序数组的中位数
# 📃 题目描述
题目链接:4. 寻找两个正序数组的中位数 (opens new window)
# 🔔 解题思路
可以直接看官方题解:https://leetcode.cn/problems/median-of-two-sorted-arrays/solution/xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-s-114/
- 要找到有序数组 nums1 和 nums2 的第 k 小的元素,我们可以比较 nums1[k/2 - 1] 和 nums2[k/2 -1]。nums1[k/2 - 1] 和 nums2[k/2 - 1] 的前面(不包括他们本身)都有 k/2 - 1 个元素
- 对于 nums1[k/2 - 1] 和 nums2[k/2 - 1] 中的最小值,最多会有 (k/2 - 1) + (k/2 - 1) = k - 2 个元素比他小,那么他就肯定不是第 k 小的数了!
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int len = nums1.length + nums2.length;
// 奇数, 中位数是第 len/2 + 1 个数
if (len % 2 == 1) {
int k = len / 2 + 1;
return findK(nums1, nums2, k);
}
// 偶数,中位数是第 len/2 和 第 len/2 + 1 个数
int k1 = len / 2;
int k2 = len / 2 + 1;
return (findK(nums1, nums2, k1) + findK(nums1, nums2, k2)) / 2;
}
// 返回 nums1 和 nums2 中第 k 小的数的值
private double findK(int[] nums1, int[] nums2, int k) {
// nums1 的下标
int index1 = 0;
// nums2 d
int index2 = 0;
while (true) {
// nums1 为空,直接 nums2 的第 k 个数就行
if (index1 == nums1.length) {
return nums2[index2 + k - 1];
}
// nums2 为空,直接 nums1 的第 k 个数就行
if (index2 == nums2.length) {
return nums1[index1 + k - 1];
}
if (k == 1) {
return Math.min(nums1[index1], nums2[index2]);
}
// nums1 和 nums2 分别取 k/2 个数
int half = k / 2;
// nums1[index1, newIndex1]
int newIndex1 = Math.min(index1 + half - 1, nums1.length - 1);
// nums2[index2, newIndex2]
int newIndex2 = Math.min(index2 + half - 1, nums2.length - 1);
if (nums1[newIndex1] <= nums2[newIndex2]) {
// 第 k 小的数肯定不在 [index1, newIndex1]
k -= newIndex1 - index1 + 1;
index1 = newIndex1 + 1;
}
else {
// 第 k 小的数肯定不在 [index2, newIndex2]
k -= newIndex2 - index2 + 1;
index2 = newIndex2 + 1;
}
}
}
}
# 💥 复杂度分析
- 空间复杂度:O(1)
- 时间复杂度:O(LogN)
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10