注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex4 Median of Two Sorted Arrays  

2015-05-29 23:06:37|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
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)).

很简单的二路归并的变形,就是不断从两个数组的头拿数组,直到找到中数的下标

class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
double result;
result = traverse(nums1,nums2);
return result;
}
double traverse(vector<int> nums1, vector<int> nums2)
{
int len1 = nums1.size();
int len2 = nums2.size();
int i, j;
int index = 0;
i = 0; //第一个数组的下标
j = 0; //第二个数组的下标
//如果是奇数的话,那么index下标就是 (len1+len2)/2
//如果是偶数的话,index的下标就是 (len1+len2-1)/2 (len1+len2+1)/2
int bound;
bool flag = (len1 + len2) % 2 == 0;
if (flag)
bound = (len1 + len2 - 1) / 2;
else
bound = (len1 + len2) / 2;

int median1, median2;
while (i<len1||j<len2)
{
if (i < len1&&j < len2)
{
if (nums1[i] <= nums2[j])
{
median1 = nums1[i];
i++;
}
else
{
median1 = nums2[j];
j++;
}
}
else if (i<len1)
{
median1 = nums1[i];
i++;
}
else
{
median1 = nums2[j];
j++;
}

if (index == bound)
break;

index++;
}
if (flag)
{
//偶数有两个 比较下一个
if (i < len1&&j < len2)
{
median2 = (nums1[i] > nums2[j]) ? nums2[j] : nums1[i];
}
else if (i<len1)
{
median2 = nums1[i];
}
else
{
median2 = nums2[j];
}
return ((double)median1 + (double)median2) / 2;
}
else
{
return (double)median1;
}
}
};


  评论这张
 
阅读(7)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017