Share my 4 kinds of java solution{"5 lines 8 ms", "12 lines 6 ms", "9 lines 4 ms", "10 lines 4ms"}


  • 0
    S
    public class Solution {
        //#method 1: 5 lines 8 ms O(log(m+n)+m+n)
         public double findMedianSortedArrays(int[] nums1, int[] nums2) {
             int[] nums3 = new int[nums1.length + nums2.length];
             System.arraycopy(nums1, 0, nums3, 0, nums1.length);
             System.arraycopy(nums2, 0, nums3, nums1.length, nums2.length);
             Arrays.sort(nums3);
             return (nums3[nums3.length >> 1] + nums3[(nums3.length - 1) >> 1]) / 2.0;
         }
        
        // #method 2: 12 lines 6 ms O(m+n)
         public double findMedianSortedArrays(int[] nums1, int[] nums2) {
             int[] nums3 = new int[nums1.length + nums2.length];
             for(int i = 0, j = 0, k = 0; i < nums1.length || j < nums2.length; ++k) {
                 if(i == nums1.length) {
                     nums3[k] = nums2[j++];
                 } else if(j == nums2.length) {
                     nums3[k] = nums1[i++];
                 } else if(nums1[i] <= nums2[j]) {
                     nums3[k] = nums1[i++];
                 } else {
                     nums3[k] = nums2[j++];
                 }
              }
             return (nums3[nums3.length >> 1] + nums3[(nums3.length - 1) >> 1]) / 2.0;
         }
    
        // #method 3: 15 lines 4 ms O(m+n)
         public double findMedianSortedArrays(int[] nums1, int[] nums2) {
             int nums1Mid = nums1.length - 1, nums2Mid = nums2.length - 1;
             while(true) {
                 int L1 = nums1Mid == -1 ? Integer.MIN_VALUE : nums1[nums1Mid >> 1];
                 int R1 = nums1Mid == (2 * nums1.length - 1) ? Integer.MAX_VALUE : nums1[(nums1Mid + 1) >> 1];
                 int L2 = nums2Mid == -1 ? Integer.MIN_VALUE : nums2[nums2Mid >> 1];
                 int R2 = nums2Mid == (2 * nums2.length - 1) ? Integer.MAX_VALUE : nums2[(nums2Mid + 1) >> 1];
                 if(L1 > R2) {
                     nums1Mid--;
                     nums2Mid++;
                 } else if(L2 > R1) {
                     nums2Mid--;
                     nums1Mid++;
                 } else {
                     return (Math.max(L1, L2) + Math.min(R1, R2)) / 2.0;
                 }
             }
         }
        
        // #method 3(shorter): 9 lines 4 ms O(m+n)
         public double findMedianSortedArrays(int[] nums1, int[] nums2) {
             int offset = 0;
             while(true) {
                 int L1 = (nums1.length - 1 - offset) == -1 ? Integer.MIN_VALUE : nums1[(nums1.length - 1 - offset) >> 1];
                 int R1 = (nums1.length - 1 - offset) == (2 * nums1.length - 1) ? Integer.MAX_VALUE : nums1[((nums1.length - 1 - offset) + 1) >> 1];
                 int L2 = (nums2.length - 1 + offset) == -1 ? Integer.MIN_VALUE : nums2[(nums2.length - 1 + offset) >> 1];
                 int R2 = (nums2.length - 1 + offset) == (2 * nums2.length - 1) ? Integer.MAX_VALUE : nums2[((nums2.length - 1 + offset) + 1) >> 1];
                 if(L1 > R2) offset++;
                 else if(L2 > R1) offset--;
                 else return (Math.max(L1, L2) + Math.min(R1, R2)) / 2.0;
             }
         }
    
        // #method 4: 12 lines 4 ms O(log(m+n))
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            if(nums1.length < nums2.length) return findMedianSortedArrays(nums2, nums1);
            int low = -1, high = 2 * nums2.length + 1;
            while(true) {
                int mid2 = (low + high) / 2;
                int mid1 = nums1.length + nums2.length - mid2;  // ==nums1.length - nums2.length + 2 * nums2.length - mid2;
                int L1 = mid1 == 0 ? Integer.MIN_VALUE : nums1[(mid1 - 1) / 2];
                int R1 = mid1 == (2 * nums1.length) ? Integer.MAX_VALUE : nums1[mid1 / 2];
                int L2 = mid2 == 0 ? Integer.MIN_VALUE : nums2[(mid2 - 1) / 2];
                int R2 = mid2 == (2 * nums2.length) ? Integer.MAX_VALUE : nums2[mid2 / 2];
                if(L1 > R2) low = (low + high) / 2;
                else if(L2 > R1) high = (low + high) / 2;
                else return (Math.max(L1, L2) + Math.min(R1, R2)) / 2.0;
            }
        }
    
        // #method 4(shorter): 10 lines 4 ms O(log(m+n))
         public double findMedianSortedArrays(int[] nums1, int[] nums2) {
             if(nums1.length < nums2.length) return findMedianSortedArrays(nums2, nums1);
             int low = -1, high = 2 * nums2.length + 1, start = nums1.length - nums2.length;
             while(true) {
                 int L1 = (start + (low + high) / 2) == 0 ? Integer.MIN_VALUE : nums1[((start + (low + high) / 2) - 1) / 2];
                 int R1 = (start + (low + high) / 2) == (2 * nums1.length) ? Integer.MAX_VALUE : nums1[(start + (low + high) / 2) / 2];
                 int L2 = (2 * nums2.length - (low + high) / 2) == 0 ? Integer.MIN_VALUE : nums2[((2 * nums2.length - (low + high) / 2) - 1) / 2];
                 int R2 = (2 * nums2.length - (low + high) / 2) == (2 * nums2.length) ? Integer.MAX_VALUE : nums2[(2 * nums2.length - (low + high) / 2) / 2];
                 if(L1 > R2) high = (low + high) / 2;
                 else if(L2 > R1) low = (low + high) / 2;
                 else return (Math.max(L1, L2) + Math.min(R1, R2)) / 2.0;
             }
         }
    }

  • 1
    K

    There is no O(log(m+n)+m+n) in the world. It should be O(m+n)


  • 0
    H

    I guess the 1st method is O((m+n)log(m+n))? It uses sort.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.