Suggest a feature
×

Welcome to TagMyCode

Please login or create account to add a snippet.
0
0
 
0
Language: Java
Posted by: YUE GU
Added: Jul 27, 2019 10:57 PM
Views: 2
Tags: no tags
  1. package Leetcode;
  2. // google   facebook
  3. // todo
  4.  
  5. /*
  6. array
  7. median
  8.  
  9.  */
  10. public class _4_MedianOfTwoSortedArrays {
  11.     /*
  12. The key point of this problem is to ignore half part of A and B each step recursively by comparing the median of remaining A and B:
  13.  
  14. if (aMid < bMid) Keep [aRight + bLeft]
  15. else Keep [bRight + aLeft]
  16.      */
  17.     public class Solution {
  18.         public double findMedianSortedArrays(int[] nums1, int[] nums2) {
  19.             // Deal with invalid corner case.
  20.             if (nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0) return 0.0;
  21.  
  22.             int m = nums1.length, n = nums2.length;
  23.             int l = (m + n + 1) / 2; //left half of the combined median
  24.             int r = (m + n + 2) / 2; //right half of the combined median
  25.  
  26.             // If the nums1.length + nums2.length is odd, the 2 function will return the same number
  27.             // Else if nums1.length + nums2.length is even, the 2 function will return the left number and right number that make up a median
  28.             return (getKth(nums1, 0, nums2, 0, l) + getKth(nums1, 0, nums2, 0, r)) / 2.0;
  29.         }
  30.  
  31.         private double getKth(int[] nums1, int start1, int[] nums2, int start2, int k) {
  32.             // This function finds the Kth element in nums1 + nums2
  33.  
  34.             // If nums1 is exhausted, return kth number in nums2
  35.             if (start1 > nums1.length - 1)
  36.                 return nums2[start2 + k - 1];
  37.  
  38.             // If nums2 is exhausted, return kth number in nums1
  39.             if (start2 > nums2.length - 1)
  40.                 return nums1[start1 + k - 1];
  41.             // base case
  42.             // If k == 1, return the first number
  43.             // Since nums1 and nums2 is sorted, the smaller one among the start point of nums1 and nums2 is the first one
  44.             if (k == 1) return Math.min(nums1[start1], nums2[start2]);
  45.  
  46.             int mid1 = Integer.MAX_VALUE;
  47.             int mid2 = Integer.MAX_VALUE;
  48.             if (start1 + k / 2 - 1 < nums1.length) mid1 = nums1[start1 + k / 2 - 1];
  49.             if (start2 + k / 2 - 1 < nums2.length) mid2 = nums2[start2 + k / 2 - 1];
  50.  
  51.             // Throw away half of the array from nums1 or nums2. And cut k in half
  52.             if (mid1 < mid2) {
  53.                 return getKth(nums1, start1 + k / 2, nums2, start2, k - k / 2); //nums1.right + nums2
  54.             } else {
  55.                 return getKth(nums1, start1, nums2, start2 + k / 2, k - k / 2); //nums1 + nums2.right
  56.             }
  57.         }
  58.     }
  59. }
  60.