4. Median of Two Sorted Arrays

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)).

You may assume nums1 and nums2 cannot be both empty.
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

Solution

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        
        int len = nums1.length + nums2.length,max = 0,min = 0;
        
        if (nums1.length == 0) {
            
            max = nums2[nums2.length-1];
            min = nums2[0];
        } else if (nums2.length == 0) {
            
            max = nums1[nums1.length-1];
            min = nums1[0];
        } else {
            
            max = nums1[nums1.length-1] > nums2[nums2.length-1] ? nums1[nums1.length-1] : nums2[nums2.length-1];
            min = nums1[0] < nums2[0] ? nums1[0] : nums2[0];
        }
        
        int[] all = new int[max + 1 - min];
        for (int i = 0; i < nums1.length; i++) {
            all[nums1[i] - min]++;
        }
        for (int i = 0; i < nums2.length; i++) {
            all[nums2[i] - min]++;
        }
        
        int index = len / 2 + 1;
        int flag = len % 2;
        int key = 0,tmp = -1;
        
        for (int i = 0; i < max + 1 - min; i++) {
            
            if (all[i] == 0) {
                continue;
            }
            key += all[i];
            
            if (flag == 1 && key >= index) {
                
                return (double)(i + min);
            }else if (flag == 0) {
                
                if (tmp != -1 && all[i] != 0) {
                    
                    return (i + tmp) / 2.0 + min;
                }
                if (key >= index) {
                    
                    return (double)(i + min);
                } else if (key == index - 1) {
                    
                    tmp = i;
                }
            }
        }
        return 0.0;
    }
}

强行用了一波桶排序。。。