leetcode4-寻找两个有序数组的中位数

蓝星 2019年12月28日 266次浏览

题目描述

给定两个大小为 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

思路

获取中位数

private double median(int nums[]){
        int len = nums.length;
	//如果是奇数,则返回中间的数
        if (len % 2 == 1){
            return nums[len / 2];
        }
	//如果是偶数则返回中间两个数的均值
        return (nums[len / 2 - 1] + nums[len / 2]) / 2.0;
    }

解法1——合并数组

既然两个数组是排好序的数组,那么我们可以将两个有序数组进行合并,找出中位数。但这种方法的时间复杂度为O(m + n),空间复杂的为O(1)

public double force(int[] nums1, int[] nums2){
        if (nums1 == null || nums1.length == 0){
            return median(nums2);
        }
        if (nums2 == null || nums2.length == 0){
            return median(nums1);
        }
        int len1 = nums1.length;
        int len2 = nums2.length;
        int times = -1;
        boolean odd = (len1 + len2) % 2 == 1;
        int half = (len1 + len2) / 2 - 1;

        int i = 0, j = 0;
	//代表中间的两位数
        int val1 = 0, val2 = 0;
        int tmpValue;
        while (i < len1 || j < len2){
            if (i == len1){
                tmpValue = nums2[j];
                j++;
            }else if (j == len2){
                tmpValue = nums1[i];
                i++;
            }else if (nums1[i] < nums2[j]){
                tmpValue = nums1[i];
                i++;
            }else {
                tmpValue = nums2[j];
                j++;
            }
            times++;
            if (times == half){
                val1 = tmpValue;
            }else if (times == half + 1){
                val2 = tmpValue;
            }
        }
        if (odd){
            return val2;
        }else {
            return (val1 + val2) / 2.0;
        }

    }

解法2——利用二分查找

既然题目中要求时间复杂度为O(log(m+n)),首先想到的就是二分查找。对于两个数组num1和num2,我们使用i和j分别切割两个数组,因为两个数组都是有序的 image.png 如图所示,我们使用i和j将两个数组进行切割,假设对两个数组进行和并,i和j所在的位置正好是中位数所在位置,那么必须满足以下两个三个条件

  1. i + j = (m + n + 1) / 2:i和j所在位置
  2. Ai <= B(j+1)
  3. Bj <= A(i+1) 只要满足2和3,则说明i和j分割正确,则Ai和Bj就位于合并后数组的中间,得到中间数
if ((m + n) % 2 == 0) {
   return (double) (Math.max(Ai, Bj) + Math.min(A(i+1), B(j+1))) / 2;
} else {
   return (double) Math.max(Ai, Bj);
}

如果Ai>B(j+1),则说明i需要向左移,如果Bj>A(i+1),则说明i需要向右移。 通过上述分析,可以转换为代码如下:

private double binarySearch(int[] nums1, int[] nums2){
        if (nums1.length > nums2.length){
            return binarySearch(nums2, nums1);
        }
        int m = nums1.length;
        int n = nums2.length;
        int low = 0, high = m;
        while (low <= high){
            // partition A position i
            int i = low + (high - low) / 2;
            // partition B position j
            int j = (m + n + 1) / 2 - i;

            int maxLeftA = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
            int minRightA = i == m ? Integer.MAX_VALUE : nums1[i];

            int maxLeftB = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
            int minRightB = j == n ? Integer.MAX_VALUE : nums2[j];

            if (maxLeftA <= minRightB && maxLeftB <= minRightA) {
                // total length is even
                if ((m + n) % 2 == 0) {
                    return (double) (Math.max(maxLeftA, maxLeftB) + Math.min(minRightA, minRightB)) / 2;
                } else {
                    // total length is odd
                    return (double) Math.max(maxLeftA, maxLeftB);
                }
            } else if (maxLeftA > minRightB) {
                // binary search left half
                high = i - 1;
            } else {
                // binary search right half
                low = i + 1;
            }
        }
        return 0;
    }