挑战程序竞赛系列（18）：3.1查找第k大的值

用户1147447

发布于 2019-05-26 09:21:49

2950

发布于 2019-05-26 09:21:49

文章被收录于专栏：机器学习入门

挑战程序竞赛系列（18）：3.1查找第k大的值

详细代码可以fork下Github上leetcode项目，不定期更新。

练习题如下：

POJ 3685: Matrix

可以发现每一列关于i是单调递增的，利用这个性质就可以二分了。这种关于查找第k大的二分模式还和我之前遇到的一般二分模式有所区别，可以观察它的while循环结构：

    while (rt - lf > 1){
        long mid = (rt + lf) / 2;
        if (check(mid)) rt = mid;
        else lf = mid;
    }
    System.out.println(rt);

嘿，这样就能找到第k大的值了，神奇。简单说明一下，因为lf和rt只会赋值成mid，所以不管抛弃左半部分还是右半部分，抛弃的都是lf-1和rt+1，当遇到<m的情况，lf = mid，表面lf-1的值都不可能是第m小的值，而>=m的情况比较特殊，在rt+1的右边也不可能是第m小的值，在rt处能够满足>=m。这说明，mid还在lf,rt范围内，接着迭代，直到rt - lf == 1的情况，为什么不是到rt == lf的情况呢？

没有必要，因为我们知道，能够使得lf = mid的情况，是check(mid)过了，而在check的返回是cnt<m的情况，所以可以这么理解：

在check(lf)处时，已经是<m的情况，所以没必要把真正的rt上界更新到lf。

另外一点也可以帮助理解这个循环式：

起码第m小的元素可能存在重复的情况，所以我们真正关注的在于<m的情况，具体有>=m的个数是多少并不关心，只要符合>=m，这个第m小的数总能被求出。

或者可以这么理解：

找到一个区间l, l + 1，满足check(l) 是 < m 的情况，而check(l+1)时，则是>=m的情况，那么自然地，这个第m小的值就是l+1了。

说明这值一定存在，否则check的累加值怎么会改变呢？

代码如下：

    static int n;
    static long m;
    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        while (N-->0){
            n = in.nextInt();
            m = in.nextLong();
            long lf = -25000000001l;
            long rt = 25000000001l;
            while (rt - lf > 1){
                long mid = (rt + lf) / 2;
                if (check(mid)) rt = mid;
                else lf = mid;
            }
            System.out.println(rt);
        }
        in.close();
    }

    //注意，需要改成long而不是int，否则在计算时，会溢出，导致WA
    public static long f(long i, long j){
        return i * i + 100000 * i + j * j - 100000 * j + i * j;
    }

    public static boolean check(long mid){

        long cnt = 0;
        for (int j = 1; j <= n; ++j){
            cnt += binarySearch(j, mid);
        }
        return cnt >= m;
    }

    public static long binarySearch(int j, long key){
        int lf = 1, rt = n;
        while (lf < rt){
            int mid = lf + (rt - lf + 1) / 2;
            if (f(mid, j) > key) rt = mid - 1;
            else lf = mid;
        }
        if (f(lf, j) <= key) return lf;
        return 0;
    }

POJ 3579:Median

有了上一题的基础，这道题就不难解决了，但没想到用Scanner居然会超时，在网上看到了一种解决方案，终于过了。

首先能想到的是对原数组进行排序，之所以排序，是因为好统计<=mid的次数，而且很直观的一个想法是，一旦排序，长度为1的间隔一定比长度为2的间隔来得小，而这些值都是我们求mid需要考虑的，有序性能很好的加快搜索。

代码如下：

    static int[] nums;
    static int N;
    static int C;
    public static void main(String[] args) throws IOException {
        StreamTokenizer st = new StreamTokenizer(new BufferedReader(  
                new InputStreamReader(System.in)));  
        while (st.nextToken()!=StreamTokenizer.TT_EOF) {  
            N = (int)st.nval;
            nums = new int[N];
            for (int i = 0; i < N; ++i){
                st.nextToken();
                nums[i] = (int)st.nval;
            }
            Arrays.sort(nums);
            C = N * (N - 1) / 2;
            int lf = 0, rt = nums[N-1] - nums[0] + 1;
            while (rt - lf > 1){
                int mid = (lf + rt) / 2;
                if (valid(mid)) rt = mid;
                else lf = mid;
            }
            System.out.println(rt);
        }
    }

    public static boolean valid(int mid){
        int cnt = 0;
        for (int i = 0; i < N - 1; ++i){
            int pos = binarySearch(nums, i + 1, N - 1, nums[i] + mid);
            if (pos != -1){
                cnt += (pos - i);
            }
        }
        return cnt >= (C + 1) / 2;
    }

    public static int binarySearch(int[] nums, int lf, int rt, int key){
        while (lf < rt){
            int mid = lf + (rt - lf + 1) / 2;
            if (nums[mid] > key) rt = mid - 1;
            else lf = mid;
        }
        if (nums[lf] <= key) return lf;
        return -1;
    }

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2017年06月23日，如有侵权请联系 cloudcommunity@tencent.com 删除

github