LeetCode #4

问题：

给定两个大小为 m 和 n 的有序数组 **nums1 **和 **nums2 **。

请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。

你可以假设 nums1 和 nums2 不同时为空。

思路：遍历。更快的解法想到了再补充。

package xyz.quxiao.play.lab.leetcode;

/**
 * 输入两个有序的数组，输出中位数 * * @author 作者 :quxiao 创建时间：2017/11/11 16:52
 */public class Problem4 {

  // 思路：确定目标索引的位置，逐个搜索
  public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int total = nums1.length + nums2.length;
    // i:nums1 j:nums2 k:merged
  int i = 0, j = 0, k = -1;
    int targetIndex = 0;
    int curValue = 0;
    int next = 0;
    // even
  if (total % 2 == 0) {
      targetIndex = (total - 2) / 2;
    } else {
      targetIndex = (total - 1) / 2;
    }

    while (i < nums1.length || j < nums2.length) {
      k++;
      if (i < nums1.length && j < nums2.length) {
        if (nums1[i] <= nums2[j]) {
          curValue = nums1[i++];
        } else {
          curValue = nums2[j++];
        }
      } else if (i < nums1.length) {
        curValue = nums1[i++];
      } else {
        curValue = nums2[j++];
      }

      if (k == targetIndex) {
        // even
  if (total % 2 == 0) {
          if (i < nums1.length && j < nums2.length) {
            next = Math.min(nums1[i], nums2[j]);
          } else if (i < nums1.length) {
            next = nums1[i];
          } else {
            next = nums2[j];
          }
          return (curValue + next) / 2.0d;
        } else {
          // odd
  return 1.0d * curValue;
        }
      }
    }
    return 0d;
  }

  public static void main(String[] args) {
    int[] nums1 = {1, 1, 3, 4, 5};
    int[] nums2 = {1};

    System.out.println(findMedianSortedArrays(nums1, nums2));
  }
}