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
胡滿超 閱讀(480)
評論(0) 編輯 收藏 引用 所屬分類:
算法 、
C++