LeetCode 4

题目

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

样例

• 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
  

思路

• 先说我的解题思路（太久没做题了，思路很怪）。我写了一个O(2*logm*logn)的算法。主要的思路是：

  • 假设：第一个数组为A，长度为m；第二个数组为B，长度为n；AB合并排序好的数组为C（并没有排序，只是为了方便说明），长度为m+n。
  • 1. 二分数组A，查找小于等于C[(m+n)/2+1]的最大的数所在的位置，二分中点的index为indexDim。
  • 2. 那么如何比较二分中点的数和C[(m+n)/2+1]的大小呢，因为A,B均有序，所以看index就行了。就对于这个A[indexDim]，在B中二分查找小于等于A[indexDim]中最大的数所在的位置L。
  • 3. 然后我只需要比较L + indexDim + 1与（m+n）/2 + 1即可。
  • 4. 交换A、B再来一次。

• 这个思想的问题在于代码写起来很麻烦，需要考虑奇数偶数的情况，特别是偶数时，还需要特殊处理(m+n)/2这个位置的数字。所以我也交了几次才AC了。并且时间复杂度上也没有O（log(m+n)）的算法优。

• 因为最近刚开始学习JAVA，所以代码质量比较低。

  // 二分第二个数组
  public int binarySearchTwo(int[] arr, int target, int flag) {
      int l = 0, r = arr.length - 1;
      if (l == r) {
        return arr[l] > target ? -1 : 0;
      }
      while (l < r) {
        int dim = (l + r) / 2 + 1;
        if ((arr[dim] < target && flag == 0) || (arr[dim] <= target && flag == 1)) {
          l = dim;
        } else {
          r = dim - 1;
        }
      }
      return (arr[l] < target && flag == 0) || (arr[l] <= target && flag == 1) ? l : -1;
  }
  
  // 二分第一个数组
  public int binarySearchOne(int[] nums1, int[] nums2, int flag) {
      int l = 0, r = nums1.length - 1, m = nums1.length + nums2.length;
      while (l < r) {
        int dim = (l + r) / 2 + 1;
        int b = this.binarySearchTwo(nums2, nums1[dim], flag) + 1;
        if (dim + b <= m / 2) {
          l = dim;
        } else {
          r = dim - 1;
        }
      }
      return l;
  }
  
  /**
  * 寻找自己前一个的数
  * @param indexOne
  * @param indexTwo
  * @return
  */
  public int maxNext(int[] num1, int[] num2, int indexOne, int indexTwo) {
      int resOne = indexOne == 0 ? -10000 : num1[indexOne - 1];
      int resTwo = indexTwo == -1 ? -10000 : num2[indexTwo];
      return Math.max(resOne, resTwo);
  }
  
  public double findMedianSortedArrays(int[] nums1, int[] nums2) {
      if (nums1.length == 0) {
        return nums2.length % 2 == 0 ? (nums2[nums2.length / 2 - 1] + nums2[nums2.length / 2]) / 2.0 : (nums2[nums2.length / 2]);
      } else if (nums2.length == 0) {
        return nums1.length % 2 == 0 ? (nums1[nums1.length / 2 - 1] + nums1[nums1.length / 2]) / 2.0 : (nums1[nums1.length / 2]);
      }
      
      int m = nums1.length + nums2.length;
      int indexOne = binarySearchOne(nums1, nums2, 0);
      int bOne = binarySearchTwo(nums2, nums1[indexOne], 0);
      int firstOne = maxNext(nums1, nums2, indexOne, bOne);
      int indexOneSum = indexOne + bOne + 2;
      int indexTwo = binarySearchOne(nums2, nums1, 1);
      int bTwo = binarySearchTwo(nums1, nums2[indexTwo], 1);
      int firstTwo = maxNext(nums2, nums1, indexTwo, bTwo);
      
      if (m % 2 == 0) {
        return indexOneSum == m / 2 + 1 ? (nums1[indexOne] + firstOne) / 2.0 : (nums2[indexTwo] + firstTwo) / 2.0;
      } else {
        return indexOneSum == m / 2 + 1 ? nums1[indexOne] : nums2[indexTwo];
      }
  }
  

• 做完以后去看了一下别人的思路就是很常规的寻找第k小的问题：

  • 当A[mid] < B[mid]时，第k小出现在（A_Right + B_Left）中。
  • 当A[mid] >= B[mid]时，第k小出现在（A_Left + B_Right）中 。
  • 并且通过（m+n+1）/2 和(m+n+2）/2的小技巧统一解决了奇数、偶数的问题。
  • 在LeetCode上两种方法跑下来时间是差不多的~

    public double findMedianSortedArrays(int[] A, int[] B) {
      int m = A.length, n = B.length;
      int l = (m + n + 1) / 2;
      int r = (m + n + 2) / 2;
      return (getKMin(A, 0, B, 0, l) + getKMin(A, 0, B, 0, r)) / 2.0;
    }
  
    public double getKMin(int[] A, int Astart, int[] B, int Bstart, int k) {
      if (Astart > A.length - 1) return B[Bstart + k - 1];
      if (Bstart > B.length - 1) return A[Astart + k - 1];
      if (k == 1) return Math.min(A[Astart], B[Bstart]);
      
      int Amin = Integer.MAX_VALUE, Bmin = Integer.MAX_VALUE;
      if (Astart + k / 2 - 1 < A.length) Amin = A[Astart + k / 2 - 1];
      if (Bstart + k / 2 - 1 < B.length) Bmin = B[Bstart + k / 2 - 1];
      
      return Amin < Bmin
        ? getKMin(A, Astart + k / 2, B, Bstart, k - k / 2)
        : getKMin(A, Astart, B, Bstart + k / 2, k - k / 2);
    }