资讯专栏INFORMATION COLUMN

Leetcode 4 Median of Two Sorted Arrays 两排序数组的中位数

wudengzan / 2596人阅读

摘要:难度为这个题目描述很清晰给出两个排序好的数组求这两个数组的中位数在解这个题的过程中会碰到以下的问题先合起来重新排序是不可行的时间复杂度太高为先归并排序也是不可行的时间复杂度为用类似桶排的方法时间复杂度为不可行可能会碰到多种全部大于或全部小于

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

Example 1:
nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:
nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

难度为Hard.

这个题目描述很清晰, 给出两个排序好的数组, 求这两个数组的中位数. 在解这个题的过程中, 会碰到以下的问题:

先合起来重新排序是不可行的, 时间复杂度太高, 为O((m+n)log(m+n))

先归并排序也是不可行的, 时间复杂度为O(m+n)

用类似桶排的方法时间复杂度为O(m+n), 不可行

可能会碰到多种case, nums1全部大于或全部小于nums2(1,2,3 4,5,6), nums1和nums2交错(2,4,6 1,3,5), 最大最小都属于其中一个序列(1,10 3,4,5), 等等

总数为奇数和偶数的处理可能会不太一样

中位数, 或者中位点旁边的两个数, 可能都位于某个数组, 也可能各自分布在两个数组中.

题目中给定的复杂度, 只能用二分查找的方法, 但是怎么在两个数组上应用呢? 我有两种通过的方法.

第一种的思路是:

假定中位数两边的数是L, R. 对总数为奇数的情况, L=R.

假定L或者R在nums1中, 按二分查找定位.

二分查找的中点游标为P, 在nums1中, 我们知道比P小, 比P大的有多少, 我们还需要知道, 在nums2中, P处于什么位置

给定P, 在nums2中二分查找, 找到比P大, 比P小的元素数目.

这样在两个数组中, 比P大的数目n1和比P小的数目n2就确定了.

我们可以调整P的位置, 直到找到L和R的值为止

由于L和R可能位于nums1或者nums2中, 所以还需要假定L或R在nums2中的情况再做一次. 同样有些细节问题需要解决.

最终程序如下:

public class Solution {

    /**
     * AC Time Complexity: O(logm*logn)
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int l1 = nums1.length;
        int l2 = nums2.length;
        if (l1 == 0) {
            if (l2 % 2 == 1) {
                return nums2[l2 / 2];
            } else {
                return ((double) nums2[l2 / 2] + nums2[l2 / 2 - 1]) / 2;
            }
        }
        if (l2 == 0) {
            if (l1 % 2 == 1) {
                return nums1[l1 / 2];
            } else {
                return ((double) nums1[l1 / 2] + nums1[l1 / 2 - 1]) / 2;
            }
        }
        List retList = new ArrayList();
        getMidLR(nums1, nums2, retList);
        getMidLR(nums2, nums1, retList);
        if (retList.size() == 0) {
            if (l2 % 2 == 1) {
                return nums2[l2 / 2];
            } else {
                return ((double) nums2[l2 / 2] + nums2[l2 / 2 - 1]) / 2;
            }
        }
        Integer sum = 0;
        for (Integer r : retList) {
            sum += r;
        }
        return (double) sum / retList.size();
    }

    public void getMidLR(int[] nums1, int[] nums2, List ret) {
        Integer midL = null;
        Integer midR = null;
        int m = nums1.length;
        int n = nums2.length;
        int l = 0;
        int r = m - 1;
        int p = m / 2;
        while (true) {
            int numSmall = 0;
            int numBig = 0;
            int tl = 0;
            int tr = n - 1;
            int tp = n / 2;
            int curVal = nums1[p];
            while (true) {
                if (tp == 0) {
                    if (nums2[0] > curVal) {
                        numSmall = 0;
                        numBig = n;
                        break;
                    } else if (nums2[0] == curVal) {
                        numSmall = 0;
                        numBig = n - 1;
                        break;
                    }
                }
                if (tp == n - 1) {
                    if (nums2[n - 1] < curVal) {
                        numSmall = n;
                        numBig = 0;
                        break;
                    } else if (nums2[n - 1] == curVal) {
                        numSmall = n - 1;
                        numBig = 0;
                        break;
                    }

                }
                if (nums2[tp] == curVal) {
                    numSmall = tp;
                    numBig = n - tp - 1;
                    break;
                }
                if (nums2[tp] < curVal && curVal < nums2[tp + 1]) {
                    numSmall = tp + 1;
                    numBig = n - tp - 1;
                    break;
                }
                if (tl == tr) {
                    break;
                }
                if (nums2[tp] > curVal) {
                    // tp move left
                    tr = tp;
                    tp = (tl + tr) / 2;
                } else {
                    // tp move right
                    tl = tp;
                    tp = (tl + tr) / 2;
                    if (tl == tp && tl < tr) {
                        tl++;
                        tp++;
                    }
                }
            }// end inner while
            int s = numSmall + p;
            int b = numBig + m - p - 1;
            if (s == b) {
                midL = midR = curVal;
                break;
            }

            if (s == (b + 1)) {
                midR = curVal;

            } else if ((s + 1) == b) {
                midL = curVal;

            }

            if (midL != null && midR != null) {
                break;
            }
            // move p
            if (l == r) {
                break;
            }
            if (s > b) {
                // p move left
                r = p;
                p = (l + r) / 2;
            } else {
                // p move right
                l = p;
                p = (l + r) / 2;
                if (l == p && l < r) {
                    l++;
                    p++;
                }
            }
        }
        if (midL != null) {
            ret.add(midL);
        }
        if (midR != null) {
            ret.add(midR);
        }
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        int[] nums11 = { 1, 3 };
        int[] nums12 = { 2 };
        System.out.println(s.findMedianSortedArrays(nums12, nums11));
        int[] nums21 = { 1, 2 };
        int[] nums22 = { 3, 4 };
        System.out.println(s.findMedianSortedArrays(nums22, nums21));
        int[] nums31 = { 1, 2, 3 };
        int[] nums32 = { 3, 4 };
        System.out.println(s.findMedianSortedArrays(nums32, nums31));
        int[] nums41 = {};
        int[] nums42 = { 1 };
        System.out.println(s.findMedianSortedArrays(nums41, nums42));
        int[] nums51 = { 1, 2 };
        int[] nums52 = { 1, 2 };
        System.out.println(s.findMedianSortedArrays(nums51, nums52));
    }
}

但问题是, 这个算法的时间复杂度是O(logm*logn), 虽然能AC, 但比题目中要求的O(log(m+n))要高.

这里还有第二种解法:
因为如果分别做二分的话, 必然会是O(logm*logn)的复杂度, 要达到题目中要求的复杂度, 需要两个数组一起做二分.

如下实现一个方法找两个数组中第n大的数:
假定需要找nums1的下标(s1,e1)范围内nums2的下标(s2,e2)范围内的第n个大小的数, 我们先把nums1和nums2各自的中点p1, p2 找出:

假定p1元素>=p2元素, 否则把nums1和nums2交换位置.

对于图中黄色的部分, 即s1~p1, s2~p2, 肯定是小于等于p1元素的, 这两块元素的数目可以求出, 定义为lmargin, 如果nth<=lmargin, 那么第nth元素必然小于p1元素, p1右边的元素可以抛弃.

问题就变成找上图的第nth元素

同样的, 依照类似的想法,

如果p1~e1, p2~e2这两部分元素的数目, 大于(元素总数-nth), 这就说明, 第nth元素, 是大于p2元素的. p2以前这块, s2~p2是可以被抛弃的.

问题就变成, 找上图的第nth - (p2 - s2) 个元素.
如此可以迭代下去, 到其中一对游标相遇的时候, 就很好解决了.

如上, 找到第n大的数, 问题就等于是解决了. 可以顺利找到中位数.

基本思路是这样, 还有些细节问题需要解决.

AC的代码如下:

public class Solution2 {
    /**
     * AC Time Complexity: O(log(m+n))
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int l1 = nums1.length;
        int l2 = nums2.length;
        // judge for empty conditions
        if (l1 == 0) {
            if (l2 % 2 == 1) {
                return nums2[l2 / 2];
            } else {
                return ((double) nums2[l2 / 2] + nums2[l2 / 2 - 1]) / 2;
            }
        }
        if (l2 == 0) {
            if (l1 % 2 == 1) {
                return nums1[l1 / 2];
            } else {
                return ((double) nums1[l1 / 2] + nums1[l1 / 2 - 1]) / 2;
            }
        }
        boolean isOdd = (l1 + l2) % 2 == 1;
        if (isOdd) {
            // if odd, just return the center one
            return findNth(nums1, 0, l1 - 1, nums2, 0, l2 - 1, (l1 + l2) / 2 + 1);
        } else {
            // if even, return the average of the center two
            return ((double) findNth(nums1, 0, l1 - 1, nums2, 0, l2 - 1, (l1 + l2) / 2)
                    + (double) findNth(nums1, 0, l1 - 1, nums2, 0, l2 - 1, (l1 + l2) / 2 + 1)) / 2;
        }
    }

    public int findNth(int[] nums1, int s1, int e1, int[] nums2, int s2, int e2, int nth) {
        // if one or two array indexes are trapped to one element
        if (s1 == e1) {
            if (s2 == e2) {
                return nth == 1 ? Math.min(nums1[s1], nums2[s2]) : Math.max(nums1[s1], nums2[s2]);
            }
            int nval = nums2[nth + s2 - 1];
            if (nval <= nums1[s1]) {
                return nval;
            } else {
                return Math.max(nums1[s1], nums2[nth + s2 - 2]);
            }
        }
        // the other trapped condition, rotate to do as the above
        if (s2 == e2) {
            return findNth(nums2, s2, e2, nums1, s1, e1, nth);
        }
        int p1 = (s1 + e1) / 2;
        int p2 = (s2 + e2) / 2;
        if (nums1[p1] >= nums2[p2]) {
            boolean f1 = false;
            boolean f2 = false;
            // number of all elements before p1(in nums1) or p2(in nums2)
            // under condition nums1[p1]>=nums2[p2],
            // all of theses elements are smaller or equal than nums1[p1]
            int lmargin = p1 - s1 + 1 + p2 - s2 + 1;
            // new indexes
            int ns1 = s1;
            int ne1 = e1;
            int ns2 = s2;
            int ne2 = e2;
            int nnth = nth;
            // if nth 0) {
                // nums1: the right of p1(including) can be discarded
                ne1 = p1 - 1;
                f1 = true;
            } else if (nth <= lmargin) {
                // nums1: the right of p1(excluding) can be discarded
                ne1 = p1;
                f1 = true;
            }
            // number of all elements after p1(in nums1) or p2(in nums2)
            // under condition nums1[p1]>=nums2[p2],
            // all of theses elements are greater or equal than nums2[p2]
            int rmargin = e1 - p1 + 1 + e2 - p2 + 1;
            // we are finding the nth element from the beginning as well as rnth
            // element from the end of the two
            int rnth = e1 - s1 + 1 + e2 - s2 + 1 - nth + 1;
            // if rnth rnth && e2 > p2) {
                // nums2: the left of p2(including) can be discarded
                nnth = nth - (p2 - s2) - 1;
                ns2 = p2 + 1;
                f2 = true;
            } else if (rmargin >= rnth) {
                // nums2: the left of p2(excluding) can be discarded
                nnth = nth - (p2 - s2);
                ns2 = p2;
                f2 = true;
            }
            if (f1 || f2) {
                // something changes, go on with the new index
                return findNth(nums1, ns1, ne1, nums2, ns2, ne2, nnth);
            }
        }
        // else reverse and find
        return findNth(nums2, s2, e2, nums1, s1, e1, nth);
    }
}

这个算法的时间复杂度可以认为是O(log(m+n)).

但其实, 我对这两个算法都不太满意, 都比较冗长复杂, 暂时还没有想到更简洁, 效率更高的算法.

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/66413.html

相关文章

  • Leetcode-4 Median of Two Sorted Arrays

    摘要:解法解法应该是最常见的一种解法,就是将两个数组头尾相加合并起来,然后重新排序,例如输入两个数组,合并之后变为,然后求出中位数。如果两个数组长度和为偶数,那么中位数有两个,否则只有一个 题目 There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the tw...

    Shihira 评论0 收藏0
  • [Leetcode] Median of Two Sorted Arrays 有序数组位数

    摘要:最新解法及思路有两个有序数组和,他们的大小各是和,请找出这两个数组所有数的中位数,总得时间复杂度不超过归并计数法复杂度时间空间思路如果对时间复杂度没有要求,这个方法是实现起来最简单的,我们只需要从下往上依次数个元素即可。 Median of Two Sorted Arrays 最新解法及思路:https://yanjia.li/zh/2018/11/... There are two...

    wuaiqiu 评论0 收藏0
  • Leetcode[4] Median of two sorted arrays

    摘要:复杂度思路因为要找中位数,又是在两个的数组里面。所以考虑用二分法。二分法经常适合的接下来考虑如何二分。然后对和进行比较,记为和。所以为了缩小搜索范围,我们可以扔掉这些数,在的剩下来的数中和的数组中接着找。说明中没有个数可以寻找。 Leetcode[4] Median of two sorted arrays There are two sorted arrays nums1 and n...

    sarva 评论0 收藏0
  • [LintCode/LeetCode] Median of two Sorted Arrays

    摘要:由于要求的时间,所以选择二分法。思路是找到两个数组合并起来的第个元素。这样只需计算两个数组的中位数是第几个元素,代入功能函数即可。据此,根据二分法的性质,我们在递归时可以将前即个元素排除。 Problem There are two sorted arrays A and B of size m and n respectively. Find the median of the tw...

    vvpvvp 评论0 收藏0
  • leetcode长跑】开个头 Median of Two Sorted Arrays

    摘要:自第一篇收集向的文章发布后,近年半没更新这个专栏了。今天是分类中第一个的,叫做。不过这样需要两个数组各扫一遍,然而我们的目的只是要取到中间值,似乎并不用完整的扫一遍。那么也就意味着,我们最终要记录的值可能是两个。 大家好,我叫张小猪。 自第一篇收集向的文章发布后,近 1 年半没更新这个专栏了。最近面试中发现将近 60% 的候选人对于 bubble sort 面露难色,于是心悸于自己也忘...

    荆兆峰 评论0 收藏0

发表评论

0条评论

wudengzan

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<