来源:力扣(LeetCode)
链接: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
-10^6 <= nums1[i], nums2[i] <= 10^6
本人提交代码
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
// 合并完的新数组最后一个元素
int newEnd = m + n - 1;
int end = m - 1;
int tail = n - 1;
while( tail >= 0 )
{
// 移动把旧元素拷贝到新数组如果这个比num2中的数都大
while( end >= 0 && nums2[tail] < nums1[end] )
{
nums1[newEnd--] = nums1[end--];
}
// 找到了插入位置,直接把num2中的最后的那个数字放到新数组
if ( newEnd >= 0 )
nums1[newEnd--] = nums2[tail];
// Next one,开始合并前一个数字
tail--;
}
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int totalLength = nums1.size() + nums2.size();
int size1 = nums1.size();
for ( int i = 0; i < nums2.size(); i++ )
nums1.push_back( 0 );
merge( nums1, size1, nums2, nums2.size() );
int mid = totalLength / 2;
return (totalLength % 2 == 0) ? (nums1[mid] + nums1[mid-1]) * 0.5f : nums1[mid];
}
};
本文由 BeijingJW 创作,采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
最后编辑时间为: Jun 2, 2023 at 05:22 pm