题目
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:
1 2 3 4 |
nums1 = [1, 3] nums2 = [2] The median is 2.0 |
Example 2:
1 2 3 4 |
nums1 = [1, 2] nums2 = [3, 4] The median is (2 + 3)/2 = 2.5 |
思路
两个排序数组找中位数,如果用类似归并排序merge的方式可以找到中间的数字,时间复杂度为O(m+n)。
本题目要求时间复杂度为O(log(m+n)),只能考虑利用已排序的特点直接按下标寻值,而不是遍历。
n个数字寻找中位数需要寻找第n/2或者n/2和n/2+1两个位置的数字,关键是如何寻找两个数组的第k小元素。
先从两个数组中一共取出k个元素,第一个数组取第k1小,第二个数组取弟k2( = k – k1)小
这样就把两个数组分成了4个部分,其中A<B, C<D
如果v1 == v2,那么它的值就正好是第k小。
如果v1<v2,那么我们可以肯定第k小的元素不会在A中,类似的v1>v2时,可以排除C
这样就把问题的规模缩小了
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
class Solution { public: int findK(vector<int>::iterator nums1, int len1, vector<int>::iterator nums2, int len2, int k) { // 我们只需要考虑nums1长度比nums2小的情况 if (len1 > len2) return findK(nums2, len2, nums1, len1, k); // 递归基 // 其中一个数组为空时 直接返回 // k==1时直接比较返回 if (len1 == 0) return nums2[k-1]; if (len2 == 0) return nums1[k-1]; if (k == 1) return min(nums1[0], nums2[0]); // 考虑k/2大于数组长度的情况 int k1 = k/2 > len1 ? len1 : k/2; int k2 = k - k1; int v1 = nums1[k1-1]; int v2 = nums2[k2-1]; if (v1 < v2) return findK(nums1 + k1, len1 - k1, nums2, len2, k - k1); else if (v1 > v2) return findK(nums1, len1, nums2 + k2, len2 - k2, k-k2); else return v1; } double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int l1 = nums1.size(); int l2 = nums2.size(); int n = l1 + l2; if (n % 2 == 0) { int f1 = findK(nums1.begin(), l1, nums2.begin(), l2, n / 2); int f2 = findK(nums1.begin(), l1, nums2.begin(), l2, n / 2 + 1); return (f1 +f2) / 2.0; } else return findK(nums1.begin(), l1, nums2.begin(), l2, n / 2 + 1); } }; |