题目大意：求两个已经排序的数组的中位数（如果合并后）。
Problem:
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)).
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 |
Idea:
Binary Search
Time complexity: O(log(min(n1,n2)))
Space complexity: O(1)
Solution: Binary Search
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 |
// Author: Huahua // Runtime: 52 ms class Solution { public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { const int n1 = nums1.size(); const int n2 = nums2.size(); // Make sure n1 <= n2 if (n1 > n2) return findMedianSortedArrays(nums2, nums1); const int k = (n1 + n2 + 1) / 2; int l = 0; int r = n1; while (l < r) { const int m1 = l + (r - l) / 2; const int m2 = k - m1; if (nums1[m1] < nums2[m2 - 1]) l = m1 + 1; else r = m1; } const int m1 = l; const int m2 = k - l; const int c1 = max(m1 <= 0 ? INT_MIN : nums1[m1 - 1], m2 <= 0 ? INT_MIN : nums2[m2 - 1]); if ((n1 + n2) % 2 == 1) return c1; const int c2 = min(m1 >= n1 ? INT_MAX : nums1[m1], m2 >= n2 ? INT_MAX : nums2[m2]); return (c1 + c2) * 0.5; } }; |
Java
|
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 |
// Author: Huahua // Runtime: 66 ms class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int n1 = nums1.length; int n2 = nums2.length; if (n1 > n2) return findMedianSortedArrays(nums2, nums1); int k = (n1 + n2 + 1) / 2; int l = 0; int r = n1; while (l < r) { int m1 = l + (r - l) / 2; int m2 = k - m1; if (nums1[m1] < nums2[m2 - 1]) l = m1 + 1; else r = m1; } int m1 = l; int m2 = k - l; int c1 = Math.max(m1 <= 0 ? Integer.MIN_VALUE : nums1[m1 - 1], m2 <= 0 ? Integer.MIN_VALUE : nums2[m2 - 1]); if ((n1 + n2) % 2 == 1) return c1; int c2 = Math.min(m1 >= n1 ? Integer.MAX_VALUE : nums1[m1], m2 >= n2 ? Integer.MAX_VALUE : nums2[m2]); return (c1 + c2) * 0.5; } } |
Related Problem:
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment