4. Find the median of two positive arrays

subject

Given two sizes, they are m and n Positive order of （ From small to large ） Array nums1 and nums2. Please find and return the values of these two positive ordered arrays Median .
The time complexity of the algorithm should be O(log (m+n)) .

Example ：

Ideas

According to the definition of the median , When m+n It's an odd number , The median is the... Of two ordered arrays (m+n)/2 Elements , When m+n When it's even , The median is the... Of two ordered arrays (m+n)/2 Elements and number (m+n)/2+1 The average of the elements . therefore , You can find the second question in the order k Small number , among k by (m+n)/2 or (m+n)/2+1.

Code

class Solution {
    
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    
        int len1 = nums1.length;
        int len2 = nums2.length;
        int totalLen = len1 + len2;
        // Odd number , The median is the... Of two ordered arrays  (m+n)/2  Elements 
        if(totalLen % 2 == 1){
    
            double median = getKthElement(nums1,nums2,totalLen/2+1);
            return median;
        }else{
    
            // Even number , The median is the... Of two ordered arrays  (m+n)/2 Elements and number  (m+n)/2+1  The average of the elements 
            double median = (getKthElement(nums1,nums2,totalLen/2) + getKthElement(nums1,nums2,totalLen/2 + 1)) / 2.0;
            return median;
        }

    }

    public int getKthElement(int[] nums1,int[] nums2,int k){
    
        int len1 = nums1.length;
        int len2 = nums2.length;
        int index1 = 0, index2 = 0;
        while(true){
    
            if(index1 == len1){
    
                return nums2[index2+k-1];
            }
            if(index2 == len2){
    
                return nums1[index1+k-1];
            }
            // We're looking for number one  1  Small numbers , So you just need to judge which number is smaller in the first two arrays 
            if(k==1){
    
                return Math.min(nums1[index1],nums2[index2]);
            }

            int half = k / 2;
            // Delete "  Some elements were added （ These elements are better than  k  Small elements should be small ） to update index Value 
            // If it exceeds the length of the array , Just point to the end of the array 
            int newIndex1 = Math.min(index1 + half,len1) - 1;
            int newIndex2 = Math.min(index2 + half,len2) - 1;
            if(nums1[newIndex1] <= nums2[newIndex2]){
    
                k -= (newIndex1-index1+1);
                index1 = newIndex1 + 1;
            }else{
    
                k -= (newIndex2-index2+1);
                index2 = newIndex2 + 1;
            }

        }

    }
}