Force buckle - 4. Find the median of two positive arrays

subject ：

Ideas ：

1. First merge the two arrays , Calculate the array separately 1 And an array 2 The length of l=m+n;

2. Define two pointers , Put them in the last position of the two arrays  ;

3. Judge , Because it's positive order （ From small to large ） Array of , So we can judge nums1 Whether the first number is greater than nums2 First number nums1[aStart]<nums2[bStart]

4. Judge , Is there any remaining number , If there is , Put it right in the back

Code ：

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        //  Composite array 
        int[] res = new int[len1+len2];
        int index = 0;
        int left = 0, right = 0;
        //  Merge and sort the composite part 
        while(left<len1&&right<len2) {
            if(nums1[left]<nums2[right]) {
                res[index++] = nums1[left++];
            } else {
                res[index++] = nums2[right++];
            }
        }
        //  Judge nums1 Remaining or nums2 The remaining , And add the rest to the composite array 
        while(left<len1) {
            res[index++] = nums1[left++];
        }
        while(right<len2) {
            res[index++] = nums2[right++];
        }
        //  Judge the length of the synthesized array , Find the median . The return is double type 
        if((len1+len2)%2==1) {
            return (double) res[(len1+len2)/2];
        } else {
            return (double) (res[(len1+len2)/2]+res[(len1+len2)/2-1])/2;
        }
    }
}

Upgrade code ：

public double findMedianSortedArrays(int[] A, int[] B) {
    int m = A.length;
    int n = B.length;
    int len = m + n;
    // left Used to save the last traversal result ,right The table looks at the result of the current traversal . Because even numbers ： Two values are required 
    int left = -1, right = -1;
    // aStart Point to the moment A The position of the array ,bStart Point to the moment B The position of the array 
    int aStart = 0, bStart = 0;
    for (int i = 0; i <= len / 2; i++) {
        //  Every time you start a new side traversal , Save the last traversal result 
        left = right;
        //  Array A The pointer aStart The condition of moving back ：aStart Not to A Last , here A The number of positions is less than B The number of positions . At this point, judge B The pointer to bStart Is it across the border? , If you cross the boundary, don't judge at this time A The value of the position is the same as B The size of the value of the position , Instead, continue to traverse A The value of the current position .
        if (aStart < m && (bStart >= n || A[aStart] < B[bStart])) {
            right = A[aStart++];
        } else {
            right = B[bStart++];
        }
    }
    if ((len & 1) == 0)
        return (left + right) / 2.0;
    else
        return right;
}

Reference link ：

(97 Bar message ) Find the median of two positive arrays _ Cold crisp - The blog of -CSDN Blog _ Find the median of two positive arrays