LeetCode - 4 寻找两个正序数组的中位数
2023-12-26 22:10:12
题目来源
4. 寻找两个正序数组的中位数 - 力扣(LeetCode)
题目描述
给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例
输入:nums1 = [1,3], nums2 = [2]
输出:2.00000
解释:合并数组 = [1,2,3] ,中位数 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
- -10^6 <= nums1[i], nums2[i] <= 10^6
题目解析
本题要求nums1和nums2合并后数组的中位数。
如果一个数组的长度n:
- n是奇数,那么数组的中位数就是 arr[arr.length / 2],即数组中间位置的元素的值
- n是偶数,那么数组的中位数就是 (arr[arr.length / 2] + arr[arr.length / 2 - 1]) / 2,即数组中间两个位置的元素的值 / 2
本题的难点主要在于如何将两个有序数组合并为一个新的有序数组。
解题思路很简单,只要定义两个指针 i, j 初始分别指向nums1和nums2的首元素,然后比较nums1[i] 和 nums2[j] 的大小,较小者元素加入到合并数组中,并且对应指针++,然后继续比较,直到某个指针越界。
假设 i 指针越界,那么 j 指针必然不会越界,即必然有一个数组会先遍历完所有元素,另一个数组无法遍历完所有元素,此时我们需要将另一个未遍历完的数组整体加入到合并数组尾部。这样就可以得到一个有序合并数组了。
Java算法源码
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int n = nums1.length + nums2.length;
int[] merge = new int[n];
int i = 0;
int j = 0;
int k = 0;
while(i < nums1.length && j < nums2.length) {
if(nums1[i] < nums2[j]) {
merge[k++] = nums1[i++];
} else {
merge[k++] = nums2[j++];
}
}
while (i < nums1.length) {
merge[k++] = nums1[i++];
}
while (j < nums2.length) {
merge[k++] = nums2[j++];
}
int mid = n / 2;
if(n % 2 == 0) {
return (merge[mid] + merge[mid - 1]) / 2.0f;
} else {
return merge[mid];
}
}
}
JS算法源码
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findMedianSortedArrays = function(nums1, nums2) {
const n = nums1.length + nums2.length;
const merge = new Array(n);
let i = 0;
let j = 0;
let k = 0;
while(i < nums1.length && j < nums2.length) {
if(nums1[i] < nums2[j]) {
merge[k++] = nums1[i++];
} else {
merge[k++] = nums2[j++];
}
}
while(i < nums1.length) {
merge[k++] = nums1[i++];
}
while(j < nums2.length) {
merge[k++] = nums2[j++];
}
const mid = Math.floor(n / 2);
if(n % 2 == 0) {
return (merge[mid] + merge[mid-1]) / 2;
} else {
return merge[mid];
}
};
Python算法源码
class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
n = len(nums1) + len(nums2)
merge = [0] * n
i = 0
j = 0
k = 0
while i < len(nums1) and j < len(nums2):
if nums1[i] < nums2[j]:
merge[k] = nums1[i]
i += 1
else:
merge[k] = nums2[j]
j += 1
k += 1
while i < len(nums1):
merge[k] = nums1[i]
i += 1
k += 1
while j < len(nums2):
merge[k] = nums2[j]
j += 1
k += 1
mid = n // 2
if n % 2 == 0:
return (merge[mid] + merge[mid - 1]) / 2.0
else:
return merge[mid]
文章来源:https://blog.csdn.net/qfc_128220/article/details/133705600
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!