寻找两个正序数组中的中位数

作者:Grey

原文地址:寻找两个正序数组中的中位数

题目链接

LeetCode 4. 寻找两个正序数组中的中位数

例如:nums1数组是 [1,2], nums2 数组是 [3,4]
那么这两个数组的合并数组是[1,2,3,4] ,所以中位数 (2 + 3) / 2 = 2.5

再比如:nums1数组是 [1,2,3], nums2 数组是 [4,5]
那么这两个数组的合并数组是[1,2,3,4,5] ,所以中位数 3

时间和空间都是O(M+N)的解法

这不是最优解,但是是最容易想到的一个解法,即,创建一个合并数组,这个数据的长度就是两个数据长度之和,然后通过合并有序数组的方法将这个合并数组生成出来,如果合并数组长度是奇数,则取中间值,如果合并长度是偶数,则取上中位数和下中位数,通过(上中位数+下中位数)/ 2 得到结果。

这个解法的时间复杂度和空间复杂度都是O(M+N), 比较简单,完整代码如下:

public double findMedianSortedArrays1(int[] nums1, int[] nums2) {
        // 题目已经说明nums1和nums2不能同时为空
        if (null == nums1 || nums1.length == 0) {
            return median(nums2);
        }
        if (null == nums2 || nums2.length == 0) {
            return median(nums1);
        }
        int m = nums1.length;
        int n = nums2.length;
        int[] nums = new int[m + n];
        int i = 0;
        int j = 0;
        int index = 0;
  // 合并两个有序数组的实现
        while (i < m && j < n) {
            if (nums1[i] >= nums2[j]) {
                nums[index++] = nums2[j++];
            } else {
                nums[index++] = nums1[i++];
            }
        }
        while (i < m) {
            nums[index++] = nums1[i++];
        }
        while (j < n) {
            nums[index++] = nums2[j++];
        }
        return median(nums);
    }
    // 求一个有序数组的中位数
    // 如果是奇数,直接返回中间位置的值
    // 如果是偶数,则返回(上中位数+下中位数)/ 2的值
    public static double median(int[] arr) {
        int len = arr.length;
        if ((len & 1) == 1) {
            // 奇数
            return arr[len / 2];
        }
        return ((arr[len / 2] + arr[(len - 1) / 2]) / 2d);
    }

时间复杂度O(log(M+N))的解法

如果我们可以高效实现如下方法:

// 在O(log(M+N))时间复杂度下找到num1和num2这两个有序数组合并后的第k大的数是什么
int findKth(int[] nums1, int[] nums2, int k)

那么题目就可以通过如下方式实现:

   public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 题目已经说明nums1和nums2不能同时为空
        if (null == nums1 || nums1.length == 0) {
            return median(nums2);
        }
        if (null == nums2 || nums2.length == 0) {
            return median(nums1);
        }
        int m = nums1.length;
        int n = nums2.length;
			
        if (((m + n) & 1) == 1) {
           // 合并后的数组长度是奇数,则取中间这个数
            return findKth(nums1, nums2, (m + n) / 2 + 1);
        }
        // 合并后的数组长度如果是偶数,则返回(上中位数+下中位数)/ 2的值
        return (findKth(nums1, nums2, (m + n) / 2) + findKth(nums1, nums2, ((m + n) / 2 + 1))) / 2d;
    }

现在所有的目光都聚焦在这个算法中,

// 在O(log(M+N))时间复杂度下找到num1和num2这两个有序数组合并后的第k大的数是什么
int findKth(int[] nums1, int[] nums2, int k)

注:以上算法中,我们规定k以1开始计算,也就是说:合并数组中最小的数是第1小的,而不是第0小的。且在调用的时候,保证1<= k <= nums1.lengh + nums2.length

在解决这个算法之前,假设我们已经有一个方法,可以高效得到:两个长度相等的排序数组合并后的上中位数,我们假设这个方法为:

// 获取两个长度相等的有序数组merge后的上中位数
// 如果是偶数,取上中位数
// 调用该方法的时候保证[s1...e1] 和 [s2...e2]等长
int getUpMedian(int[] A, int s1, int e1, int[] B, int s2, int e2) 

一旦我们有getUpMedian这个方法,我们就可以针对k的取值,分多种情况来解决findKth方法,我们假设

int findKth(int[] nums1, int[] nums2, int k)

方法中,较长的数组我们重新定义为名字为longs的数组,较短的数组重新定义为名字shorts的数组。

现在开始讨论k的范围:

第一种情况:k<=shorts.length

在这种情况下比较简单,我们可以将longs数组取前k个数,shorts数组取前k个数,然后调用getMedian方法,拿到中位数,即是longs和shorts数组合并后的第k小的数。

例如:shorts数组为[1,3,5,7],longs数组为[2,4,6,8,10,12]
如果要取第2小的数, 客观上第2小的数是2,可能存在的范围是shorts的前2个数中,也可能存在在longs的前2个数中,除此之外,不能是其他范围,因为超过这个范围,就不止第2小了。

第二种情况:shorts.length<k<=longs.length

在这种情况下,shorts数组中的每个数都有可能,longs数组可以排除掉 前(k – shorts.len – 1) 个数,以及[kth + 1……longs.length]区间的所有数,但是要手动验证一下long中第(k- shorts.len)位置上的数是不是比shorts最后一个数大,
如果是,longs中第(k – shorts.length)位置上的数即为第k小的数,
如果不是,longs中第(k – shorts.length)位置上的数直接排除掉,
longs中剩余数和shorts中所有数用一次getUpMedian方法求得的值即为第k小的数。

例如:shorts数组为[1,3,5,7],longs数组为[2,4,6,8,10,12,14,16,18]
求第7小的数,此时shorts中的数都有可能是第7小的数,但是,longs中,可以排除如下位置的数

首先:从第8小的数开始一直到第longs.length小的数都可以排除。

其次, 7 – shorts.length – 1 即:7 – 4 – 1 = 3 ,longs中第3小之前的数都可以排除,

排除完毕后,验证一下longs中第3小的数是不是比shorts中最后一个数大,如果是,则longs中第3小的数即位两个数组的第7小的数。

如果不是,则longs中剩余可选的数继续和shorts调用getUpMedian方法。

第三种情况:longs.length<=k<=(shorts.length+longs.length)

这种情况下,shorts中可排除掉前面(k – longs.length)个数,longs中排除掉前( k – shorts.length – 1) 个数,然后手动判断下shorts和longs中剩余数中最左边的数是不是第k小的数,如果是,直接返回,如果不是,排除掉这些数,然后将shorts和longs剩余数用getUpMedian获取的结果即为答案。
例如:shorts数组为 [1,3,5,7,9,11] 长度是6,longs数组为 [2,4,6,8,10,12,14,16,18,20,22,24] 长度是12,假设要求第15小的数,那么在shorts中可以排除掉前面(15 – longs.length – 1)= 2个数, 因为即便shorts中第1小的数比longs中所有数都大,它也只能算第13小的数,第2小的数即便比longs中所有数都大,也只能算全局第14小的数。longs中可以排除掉第1一直到第8小(即:15 – shorts.length – 1 = 8)的数,因为longs中第8小的数即便比shorts数所有数都大,也只能是全局第14小的数。经过排除后,shorts中和longs中可选范围为(以下数组中没打x的数字)

shorts中为[x,x,5,7,9,11]

longs中为[x,x,x,x,x,x,x,x,18,20,22,24]

先手动判断一下,longs中的18和shorts中的5是否是第15小的数,如果是则直接返回,如果不是,shorts中[7,9,11] 和 longs中 [20,22,24] 使用getUpMedian获取的结果即为答案。

所有情况说明完毕,而且三种情况仅依赖getUpMedian 方法。所以,现在看getUpMedian 方法的实现,具体说明见注释:

// 获取两个长度相等的有序数组merge后的上中位数
// 如果是偶数,取上中位数
// 调用该方法的时候保证[s1...e1] 和 [s2...e2]等长
    public static int getUpMedian(int[] A, int s1, int e1, int[] B, int s2, int e2) {
        if (s1 == e1) {
          // 说明A和B分别只有一个数,因为求上中位数,所以取A[s1]和B[s2]的最小值
            return Math.min(A[s1], B[s2]);
        }
        int mid1 = (s1 + e1) / 2;
        int mid2 = (s2 + e2) / 2;
      // 如果A和B的中位数值一样,则这个中位数值也是A和B合并后的中位数值
        if (A[mid1] == B[mid2]) {
            return A[mid1];
        }
        boolean even = ((e1 - s1) & 1) != 0; // 是否是偶数
        if (even) {
          // 通过类似二分的方式,判断A和B的中位数可能出现的位置,
            if (A[mid1] > B[mid2]) {
               // 如果A[mid1] > B[mid2]
              // 则全局的中位数只可能在A的[s1..mid1]以及B的[mid2+1..e2]范围内产生
              // 下面的判断类似。
                return getUpMedian(A, s1, mid1, B, mid2 + 1, e2);
            } else {
                return getUpMedian(A, mid1 + 1, e1, B, s2, mid2);
            }
        } else {
            if (A[mid1] > B[mid2]) {
                if (B[mid2] > A[mid1 - 1]) {
                    return B[mid2];
                }
                return getUpMedian(A, s1, mid1 - 1, B, mid2 + 1, e2);
            } else {
                if (A[mid1] > B[mid2 - 1]) {
                    return A[mid1];
                }
                return getUpMedian(A, mid1 + 1, e1, B, s2, mid2 - 1);
            }
        }
    }

getUpMedian通过类似二分查找的方法,来得到中位数信息,复杂度就是O(log(M+N))。完整代码见:

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 题目已经说明nums1和nums2不能同时为空
        if (null == nums1 || nums1.length == 0) {
            return median(nums2);
        }
        if (null == nums2 || nums2.length == 0) {
            return median(nums1);
        }
        int m = nums1.length;
        int n = nums2.length;

        if (((m + n) & 1) == 1) {
            return findKth(nums1, nums2, (m + n) / 2 + 1);
        }
        return (findKth(nums1, nums2, (m + n) / 2) + findKth(nums1, nums2, ((m + n) / 2 + 1))) / 2d;
    }
    public static double median(int[] arr) {
        int len = arr.length;
        if ((len & 1) == 1) {
            // 奇数
            return arr[len / 2];
        }
        return ((arr[len / 2] + arr[(len - 1) / 2]) / 2d);
    }
   
    public static int findKth(int[] nums1, int[] nums2, int k) {
        int[] longs = nums1.length > nums2.length ? nums1 : nums2;
        int[] shorts = nums1 == longs ? nums2 : nums1;
        int maxLen = longs.length;
        int minLen = shorts.length;
        // k<= minLen
        // longs截取前k个数,shorts截取前k个数,两个长度相等的数组取上中位数
        if (k <= minLen) {
            return getUpMedian(shorts, 0, k - 1, longs, 0, k - 1);
        }
        // k > minLen 且 k <= maxLen
        // 到这里一定k > minLen
        if (k <= maxLen) {
            // 可以排除
            // longs中比第k小的数还大的所有数都可以排除,即下标为:[k....maxLen - 1]
            // longs中第1小到第(k - minLen - 1)小的数都可以排除
            // shorts中所有数都有可能

            // 手动验证
            // longs中第 (k - minLen) 大的数是否比shorts中最后一个数大,如果是,这个数直接就是结果
            if (longs[k - minLen - 1] >= shorts[minLen - 1]) {
                return longs[k - minLen - 1];
            }
            // 其他的数
            return getUpMedian(shorts, 0, minLen - 1, longs, k - minLen, k - 1);
        }
        // k > maxLen 且 k <= maxLen + minLen
        // 到这里一定 k > maxLen 且 k <= maxLen + minLen
      
      
        // 可以排除
        // shorts中从第1小一直到第k - maxLen - 1小的数都可以排除
        // longs中第1小的数一直到第k - minLen - 1小的数都可以排除

        // 手动验证
        if (shorts[minLen - 1] <= longs[k - minLen - 1]) {
            return longs[k - minLen - 1];
        }
        if (longs[maxLen - 1] <= shorts[k - maxLen - 1]) {
            return shorts[k - maxLen - 1];
        }
        // 其他的数
        return getUpMedian(shorts, k - maxLen, minLen - 1, longs, k - minLen, maxLen - 1);
    }

    public static int getUpMedian(int[] A, int s1, int e1, int[] B, int s2, int e2) {
        if (s1 == e1) {
            return Math.min(A[s1], B[s2]);
        }
        int mid1 = (s1 + e1) / 2;
        int mid2 = (s2 + e2) / 2;
        if (A[mid1] == B[mid2]) {
            return A[mid1];
        }
        boolean even = ((e1 - s1) & 1) != 0; // 是否是偶数
        if (even) {
            if (A[mid1] > B[mid2]) {
                return getUpMedian(A, s1, mid1, B, mid2 + 1, e2);
            } else {
                return getUpMedian(A, mid1 + 1, e1, B, s2, mid2);
            }
        } else {
            if (A[mid1] > B[mid2]) {
                if (B[mid2] > A[mid1 - 1]) {
                    return B[mid2];
                }
                return getUpMedian(A, s1, mid1 - 1, B, mid2 + 1, e2);
            } else {
                if (A[mid1] > B[mid2 - 1]) {
                    return A[mid1];
                }
                return getUpMedian(A, mid1 + 1, e1, B, s2, mid2 - 1);
            }
        }
    }
}

更多

算法和数据结构笔记

    原文作者:Grey Zeng
    原文地址: https://www.cnblogs.com/greyzeng/p/16324785.html
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞