Median of Two Sorted Arrays
2019-08-16 07:51:53来源:博客园 阅读 ()
Median of Two Sorted Arrays
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)).
You may assume nums1 and nums2 cannot be both empty.
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
Code:
//
// main.cpp
// 中位数
//
// Created by mac on 2019/7/17.
// Copyright ? 2019 mac. All rights reserved.
//
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
double midenum;
if (nums1.size()>0 && nums2.size()>0) {
for (int i=0; i<nums2.size(); ++i) {
nums1.push_back(nums2[i]);
}
sort(nums1.begin(), nums1.end());
if (nums1.size()%2==0) {
midenum=(double)((double)(nums1[nums1.size()/2])+(double)(nums1[nums1.size()/2-1]))/2;
}else{
midenum=nums1[nums1.size()/2];
}
}else if (nums1.size()>0){
if (nums1.size()%2==0) {
midenum=((double)(nums1[nums1.size()/2])+(double)(nums1[nums1.size()/2-1]))/2;
}else{
midenum=nums1[nums1.size()/2];
}
}else{
if (nums2.size()%2==0) {
midenum=((double)(nums2[nums2.size()/2])+(double)(nums2[nums2.size()/2-1]))/2;
}else{
midenum=nums2[nums2.size()/2];
}
}
return midenum;
}
};
int main(int argc, const char * argv[]) {
vector<int> a,b;
// a.push_back(1);
// a.push_back(2);
b.push_back(2);
b.push_back(3);
Solution so;
cout<<so.findMedianSortedArrays(a, b)<<endl;
return 0;
}
运行结果
2.5
Program ended with exit code: 0
参考文献
- https://leetcode.com/problems/median-of-two-sorted-arrays/
原文链接:https://www.cnblogs.com/overlows/p/11214308.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:二分法(一):二分法的基本思想
- CodeForces 710D Two Arithmetic Progressions 2020-03-06
- Add Two Numbers 2019-08-16
- Two Sum 2019-08-16
- poj-2236 wireless network(并查集) 2018-12-04
- BZOJ3732: Network(Kruskal重构树) 2018-07-22
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash