题目描述：

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

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

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

示例 1:

nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0

示例 2:

nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5

分析解答

这个题目是LeetCode上的hard题目，我的想法很简单，找出所有情况，可以提前结束循环的，就立即退出。 大概有以下几种：

  1. len1==0,len2!=0
  2. len1!=0,len2==0
  3. len1+len2为奇数
  4. len1+len2为偶数

代码实现：

package hard;

import org.omg.PortableInterceptor.SYSTEM_EXCEPTION;

/**
 * 寻找两个有序数组的中位数
  */ public class H4 {
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 =nums2.length;
        int len3 = len1+len2;
        int[] nums3 = new int[len3];       //新数组
  if (len1==0) return len2%2==0 ? (nums2[len2/2-1]+nums2[len2/2])/2.0 : nums2[len2/2];
        if (len2==0) return len1%2==0 ? (nums1[len1/2-1]+nums1[len1/2])/2.0 : nums1[len1/2];
        int i=0,j=0,k=0;
        if (len3 %2 ==0){
            while (i < len1 || j < len2){
                if (i==len1) {
                    nums3[k] = nums2[j];
                    j++;
                }else if (j==len2){
                    nums3[k] = nums1[i];
                    i++;
                }else if (nums1[i]< nums2[j]){
                    nums3[k] = nums1[i];
                    i++;
                }else {
                    nums3[k] = nums2[j];
                    j++;
                }
                if (k == len3/2) return (nums3[k]+nums3[k-1]) / 2.0;
                k++;
            }
        }else {
            while (i<len1 || j<len2){
                if (i==len1){
                    nums3[k] = nums2[j];
                    j++;
                }else if (j==len2){
                    nums3[k] = nums1[i];
                    i++;
                }else if (nums1[i]< nums2[j]){
                    nums3[k] = nums1[i];
                    i++;
                }else {
                    nums3[k] = nums2[j];
                    j++;
                }
                if (k == len3/2) return nums3[k];
                k++;
            }
        }

        return 0;
    }

    public static void main(String[] args) {
        int[] nums2 = {1,3};
        int[] nums1 = {2};
        double out = findMedianSortedArrays(nums1,nums2);
        System.out.println(out);
    }
}

结果

执行结果：

通过

显示详情

执行用时 :3 ms, 在所有 Java 提交中击败了99.53% 的用户

内存消耗 :47.4 MB, 在所有 Java 提交中击败了93.06%的用户