随笔 - 89  文章 - 118  trackbacks - 0
<2018年6月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

留言簿(16)

随笔分类(56)

随笔档案(89)

文章分类

推荐博客

搜索

  •  

最新随笔

最新评论

阅读排行榜

There are two sorted arrays A and B 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)).

The following code is better than most of the results returned by baidu or google. Time complexity is O((m+n)/2), Space complexity is O(1).

 1 double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) 
 2 {
 3     int nums1_i = 0, nums2_i = 0; 
 4     int mid1 = 0, mid2 = 0, count = 0;
 5     while (nums1_i < nums1.size() && nums2_i < nums2.size()) 
 6     {
 7         if (count++ > ((nums1.size() + nums2.size()) / 2))    break;
 8         mid1 = mid2;
 9         mid2 = (nums1[nums1_i] < nums2[nums2_i] ? nums1[nums1_i++] : nums2[nums2_i++]);
10     }  
11 
12     while (nums1_i < nums1.size()) 
13     {  
14         if (count++ > ((nums1.size() + nums2.size()) / 2))    break;
15         mid1 = mid2;
16         mid2 = nums1[nums1_i++];
17     }  
18 
19     while (nums2_i < nums2.size()) 
20     {  
21         if (count++ > ((nums1.size() + nums2.size()) / 2))    break;
22         mid1 = mid2;
23         mid2 = nums2[nums2_i++];
24     }  
25 
26     return (nums1.size() + nums2.size()) % 2 == 0 
27         ? (mid1 + mid2) / 2.0
28         : mid2; 
29 }
posted on 2018-06-26 13:57 胡满超 阅读(367) 评论(0)  编辑 收藏 引用 所属分类: 算法C++

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理