leetcode 4. Median of Two Sorted Arrays 寻找两个正序数组的中位数(困难)
2023-09-11 14:22:52 时间
一、题目大意
标签: 查找
https://leetcode.cn/problems/median-of-two-sorted-arrays
给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 1:
输入:nums1 = [1,3], nums2 = [2]
输出:2.00000
解释:合并数组 = [1,2,3] ,中位数 2
示例 2:
输入:nums1 = [1,2], nums2 = [3,4]
输出:2.50000
解释:合并数组 = [1,2,3,4] ,中位数 (2 + 3) / 2 = 2.5
提示:
- nums1.length == m
- nums2.length == n
- 0 <= m <= 1000
- 0 <= n <= 1000
- 1 <= m + n <= 2000
- -106 <= nums1[i], nums2[i] <= 106
二、解题思路
号称leetcode守门员的题。中位数可以来自于同一个数组,也可以来自于两个数组,可以是一个数,也可以是两个数。
实现思路(参考花花酱的讲解)
分类:
思路:假设n1,n2是两个数组的元素,那么k=(n1+n2+1)/2就表示左中位数或中位数的索引,假设从nums1中取m1个元素,从nums2中取m2个元素,那么m1+m2 = k。我们要求的中位数就是从max(nums[m1-1], nums[m2-1])和min(nums[m1], nums[m2])。
三、解题方法
3.1 Java实现
public class Solution2 {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int n1 = nums1.length;
int n2 = nums2.length;
// 对长度小的数组做二分搜索
if (n1 > n2 ) {
return findMedianSortedArrays(nums2, nums1);
}
// 偶数情况:nums1=>[1, 2, 3] nums2=>[3, 4, 5] 中位数 2 3
// 奇数情况:nums1=>[1, 2, 3] nums2=>[2, 3, 4, 5] 中位数 3
// nums1=>[-1, 1, 3, 5, 7, 9] nums2=>[2, 4, 6, 8, 10, 12, 14, 16]
int l = 0;
int r = n1;
// 偶数情况:左中位数 奇数情况:中位数
int k = (n1 + n2 + 1) / 2;
while (l < r) {
int m1 = l + (r - l) / 2;
int m2 = k - m1;
if (nums1[m1] < nums2[m2-1]) {
l = m1 + 1;
} else {
r = m1;
}
}
int m1 = l;
int m2 = k - l;
int c1 = Math.max(m1 < 1 ? Integer.MIN_VALUE : nums1[m1-1], m2 < 1 ? Integer.MIN_VALUE : nums2[m2-1]);
// 奇数情况
if ((n1 + n2) % 2 == 1) {
return c1;
}
int c2 = Math.min(m1 >= n1 ? Integer.MAX_VALUE : nums1[m1], m2 >= n2 ? Integer.MAX_VALUE : nums2[m2]);
return (c1 + c2) * 0.5;
}
}
四、总结小记
- 2022/5/30 做不出来的题就参考别人的吧,再转为自己的思路吧
相关文章
- Leetcode: Peeking Iterator
- [LeetCode]Delete Node in a Linked List
- 后缀数组的应用:[Leetcode] 321.拼接最大数(困难)
- JS leetcode 两个数组的交集I II 合集题解分析
- JS leetcode 寻找数组的中心索引 题解分析
- LeetCode 33. 搜索旋转排序数组
- 155、【动态规划】leetcode ——474. 一和零:三维数组+二维滚动数组(C++版本)
- 71、【哈希表】leetcode——350. 两个数组的交集 II(C++版本)
- 60、【数组】leetcode——904. 水果成篮-滑动窗口:最大窗口(C++版本)
- 60、【数组】leetcode——209. 长度最小的子数组-滑动窗口:最小窗口(C++、Python版本)
- LeetCode Search in Rotated Sorted Array 在旋转了的数组中查找
- [LeetCode] 1031. Maximum Sum of Two Non-Overlapping Subarrays 两个不重叠的子数组的最大和
- [LeetCode] 1013. Partition Array Into Three Parts With Equal Sum 将数组分成和相等的三个部分
- [LeetCode] 954. Array of Doubled Pairs 两倍数对儿数组
- [LeetCode] 829. Consecutive Numbers Sum 连续数字之和
- [LeetCode] 907. Sum of Subarray Minimums 子数组最小值之和
- [LeetCode] 898. Bitwise ORs of Subarrays 子数组按位或操作
- [LeetCode] Maximum Sum of 3 Non-Overlapping Subarrays 三个非重叠子数组的最大和
- [LeetCode] Binary Number with Alternating Bits 有交替位的二进制数
- [LeetCode] Maximum Average Subarray I 子数组的最大平均值
- [LeetCode] Find the Derangement of An Array 找数组的错排
- [LeetCode] 421. Maximum XOR of Two Numbers in an Array 数组中异或值最大的两个数字
- [LeetCode] 238. Product of Array Except Self 除本身之外的数组之积
- leetcode 643. Maximum Average Subarray I 子数组最大平均数 I
- leetcode算法88.合并两个有序数组