LeetCode[Algorithms] 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)).

{% highlight java %} package com.coderli.leetcode.algorithms;

/**

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

• @author li.hzh

• @date 2015/9/6 10:42 */ public class MedianOfTwoSortedArrays {

  public static void main(String[] args) { Solution solution = new MedianOfTwoSortedArrays().new Solution(); int[] arrayOne = new int[]{1}; int[] arrayTwo = new int[]{}; System.out.println(solution.findMedianSortedArrays(arrayOne, arrayTwo)); }

  public class Solution {

  public double findMedianSortedArrays(int[] nums1, int[] nums2) { int lengthOne = nums1.length; int lengthTwo = nums2.length; int totalLength = lengthOne + lengthTwo; int mid = totalLength / 2; if (totalLength % 2 == 1) { return findKth(nums1, nums2, mid, 0, lengthOne - 1, 0, lengthTwo -1); } else { double one = findKth(nums1, nums2, mid, 0, lengthOne - 1, 0, lengthTwo -1); double two = findKth(nums1, nums2, mid - 1, 0, lengthOne - 1, 0, lengthTwo -1); return (one + two) / 2; } }

  private int findKth(int A[], int B[], int k, int aStart, int aEnd, int bStart, int bEnd) {

  Code 27 行

  行号 复制

  1  int aLen = aEnd - aStart + 1;
  2  int bLen = bEnd - bStart + 1;
  3
  4  if (aLen == 0)
  5     return B[bStart + k];
  6  if (bLen == 0)
  7     return A[aStart + k];
  8  if (k == 0)
  9     return A[aStart] < B[bStart] ? A[aStart] : B[bStart];
  10
  11  int aMid = aLen * k / (aLen + bLen);
  12  int bMid = k - aMid - 1;
  13
  14  aMid = aMid + aStart;
  15  bMid = bMid + bStart;
  16
  17  if (A[aMid] > B[bMid]) {
  18     k = k - (bMid - bStart + 1);
  19     aEnd = aMid;
  20     bStart = bMid + 1;
  21  } else {
  22     k = k - (aMid - aStart + 1);
  23     bEnd = bMid;
  24     aStart = aMid + 1;
  25  }
  26
  27  return findKth(A, B, k, aStart, aEnd, bStart, bEnd);
  28

  } } } {% endhighlight %}

参考：http://www.programcreek.com/2012/12/leetcode-median-of-two-sorted-arrays-java/