leetcode 4. Median of Two Sorted Arrays
2024-10-13 12:27:26
https://leetcode.com/problems/median-of-two-sorted-arrays/
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
Example 1:
nums1 = [1, 3]
nums2 = [2] The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4] The median is (2 + 3)/2 = 2.5 第一种思路:采用最暴力的方法,因为给的两个数组都已经排序了,也知道中位数是第几个,直接采用二分归并排序到中位数。
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
vector<int> nums3;
int i=,j=,k=;
int m =(nums1.size()+nums2.size());
while(i<nums1.size()&&j<nums2.size()) {
if(nums1[i]<nums2[j])
nums3.push_back(nums1[i++]);
else
nums3.push_back(nums2[j++]);
k++;
if(k>m/)
{
if(m%)
return nums3[k-];
else
return (nums3[k-]+nums3[k-])/2.0;
}
}
while(i<nums1.size()){
nums3.push_back(nums1[i++]);
k++;
if(k>m/)
{
if(m%)
return nums3[k-];
else
return (nums3[k-]+nums3[k-])/2.0;
}
}
while(j<nums2.size()){
nums3.push_back(nums2[j++]);
k++;
if(k>m/)
{
if(m%)
return nums3[k-];
else
return (nums3[k-]+nums3[k-])/2.0;
}
}
return ;
}
};
在leetcode中时间为48ms。
最新文章
- ABP源码分析十四:Entity的设计
- jquery的bind跟on绑定事件的区别
- 移动端用js与jquery实时监听输入框值的改动
- 《数据结构与算法Python语言描述》习题第二章第二题(python版)
- Java线程中带有返回值的线程Callable
- PHP form 表单传参明细研究
- 【BZOJ-3697&;3127】采药人的路径&;YinandYang 点分治 + 乱搞
- 技术英文单词贴--E
- php 继承
- 【基础知识】.Net基础加强11天
- 网络编程:socket--python核心编程(3),chapter 1
- poj 3295 Tautology (构造)
- windows 环境下安装plpython语言环境到postgresql数据库
- H5 Bgsound
- python---scrapy之MySQL同步存储
- 用Beautifulsoup 来爬取贴吧图片
- nodeJs配置
- Vue之双向数据绑定
- 我今天遇到的条件语句Integer类型的
- [jzoj]3777.最短路(shortest)