LeetCode：4. Median of Two Sorted Arrays 两个排序数组的中值

我就是我 2021-06-24 15:57 306阅读 0赞

## **一、题目** ##

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:  
nums1 = \[1, 3\]  
nums2 = \[2\]

The median is 2.0  
Example 2:  
nums1 = \[1, 2\]  
nums2 = \[3, 4\]

## The median is (2 + 3)/2 = 2.5   **二、代码** ##

简单合并，排序，取中值

class Solution {
    public:
        double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {	
            int *it;
            int m = nums1.size()?nums1.size():0;
            int n = nums2.size()?nums2.size():0;
            int *merge = new int[m+n];
    
            if(!nums1.empty()){
                it = &*nums1.begin();
                memcpy(merge,it,sizeof(int)*m);   
            }
            if(!nums2.empty()){
                it = &*nums2.begin();
                memcpy(merge+m,it,sizeof(int)*n);  
            }
            sort(merge,merge+m+n);
            //注意数组下标和计算的下标区别
            return (m+n)%2?1.0*merge[(m+n)>>1]:(merge[(m+n-1)>>1]+merge[(m+n)>>1])/2.0;
            
        }
    };

class Solution {
        public double findMedianSortedArrays(int[] A, int[] B) {
            int m = A.length;
            int n = B.length;
            if (m > n) {
                int[] temp = A; A = B; B = temp;
                int tmp = m; m = n; n = tmp;
            }
            
            int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
            while (iMin <= iMax) {
                int i = (iMin + iMax) / 2;
                int j = halfLen - i;
                if (i < iMax && B[j-1] > A[i]){
                    iMin = i + 1; // i is too small
                }else if (i > iMin && A[i-1] > B[j]) {
                    iMax = i - 1; // i is too big
                }else { // i is perfect
                    int maxLeft = 0;
                    if (i == 0) { maxLeft = B[j-1]; }
                    else if (j == 0) { maxLeft = A[i-1]; }
                    else { maxLeft = Math.max(A[i-1], B[j-1]); }
                    if ( (m + n) % 2 == 1 ) { return maxLeft; }
    
                    int minRight = 0;
                    if (i == m) { minRight = B[j]; }
                    else if (j == n) { minRight = A[i]; }
                    else { minRight = Math.min(B[j], A[i]); }
    
                    return (maxLeft + minRight) / 2.0;
                }
            }
            return 0.0;
        }
    }