4. Median of Two Sorted Arrays
Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
The overall run time complexity should be O(log (m+n)).
?
Example 1:
Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.
Example 2:
Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
Constraints:
- nums1.length == m
- nums2.length == n
- 0 <= m <= 1000
- 0 <= n <= 1000
- 1 <= m + n <= 2000
- ? 1 0 6 < = n u m s 1 [ i ] , n u m s 2 [ i ] < = 1 0 6 -10^6 <= nums1[i], nums2[i] <= 10^6 ?106<=nums1[i],nums2[i]<=106
From: LeetCode
Link: 4. Median of Two Sorted Arrays
Solution:
Ideas：
In this code, findMedianSortedArrays function takes two sorted arrays nums1 and nums2, along with their sizes nums1Size and nums2Size, and returns the median of the combined array.文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-738461.html
The algorithm first ensures that nums1 is the smaller array to optimize the binary search. It then performs a binary search on the smaller array, trying to find a partition such that the elements on the left side of the partition from both arrays are smaller than the elements on the right side of the partition from both arrays. Once the correct partition is found, it calculates the median based on the combined size of both arrays being even or odd.文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-738461.html
Code:
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
// Ensure nums1 is the smaller array
if (nums1Size > nums2Size) {
return findMedianSortedArrays(nums2, nums2Size, nums1, nums1Size);
}
int x = nums1Size;
int y = nums2Size;
int low = 0;
int high = x;
while (low <= high) {
int partitionX = (low + high) / 2;
int partitionY = (x + y + 1) / 2 - partitionX;
int maxX = (partitionX == 0) ? INT_MIN : nums1[partitionX - 1];
int maxY = (partitionY == 0) ? INT_MIN : nums2[partitionY - 1];
int minX = (partitionX == x) ? INT_MAX : nums1[partitionX];
int minY = (partitionY == y) ? INT_MAX : nums2[partitionY];
if (maxX <= minY && maxY <= minX) {
// We have partitioned array at correct place
if ((x + y) % 2 == 0) {
return ((double) fmax(maxX, maxY) + fmin(minX, minY)) / 2;
} else {
return (double) fmax(maxX, maxY);
}
} else if (maxX > minY) {
high = partitionX - 1;
} else {
low = partitionX + 1;
}
}
// If input arrays are not sorted or not valid
return -1.0;
}
到了這里，關(guān)于LeetCode //C - 4. Median of Two Sorted Arrays的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
