专栏首页desperate633LeetCode 215. Kth Largest Element in an Array分析

LeetCode 215. Kth Largest Element in an Array分析

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element. For example, Given [3,2,1,5,6,4] and k = 2, return 5. Note: You may assume k is always valid, 1 ≤ k ≤ array's length. 在数组中找到第k大的元素 注意事项 你可以交换数组中的元素的位置 样例 给出数组 [9,3,2,4,8],第三大的元素是 4 给出数组 [1,2,3,4,5],第一大的元素是 5,第二大的元素是 4,第三大的元素是 3,以此类推

分析

这个一个经典的寻找第k大数的问题,我们可以有很多种解法,下面我们一一介绍。

1直接排序

显然最简单的思想就是排序,然后取出倒数第k个元素就可以了,我们可以直接调用内部的排序函数。

public int findKthLargest(int[] nums, int k) {
        final int N = nums.length;
        Arrays.sort(nums);
        return nums[N - k];
}

** O(N lg N) running time + O(1) memory **

图片.png

在用例不多,数据量不大的时候,这种简单的方法,效率反而很高,超过大部分算法

2 利用堆

从第k大元素我们自然想到堆的性质,我们可以维护一个只有k个元素的最小堆,遍历一遍所有元素,组后留下的k个就是前k大的元素

public int findKthLargest(int[] nums, int k) {

    final PriorityQueue<Integer> pq = new PriorityQueue<>();
    for(int val : nums) {
        pq.offer(val);

        if(pq.size() > k) {
            pq.poll();
        }
    }
    return pq.peek();
}

** O(N lg K) running time + O(K) memory **

图片.png

3 快排思想

利用快排的partiton思想,这种方法在最好情况下,可以达到线性时间,但是如果输入是有序的,则是最坏情况,会达到平方时间的复杂度

public int findKthLargest(int[] nums, int k) {

        k = nums.length - k;
        int lo = 0;
        int hi = nums.length - 1;
        while (lo < hi) {
            final int j = partition(nums, lo, hi);
            if(j < k) {
                lo = j + 1;
            } else if (j > k) {
                hi = j - 1;
            } else {
                break;
            }
        }
        return nums[k];
    }

    private int partition(int[] a, int lo, int hi) {

        int i = lo;
        int j = hi + 1;
        while(true) {
            while(i < hi && less(a[++i], a[lo]));
            while(j > lo && less(a[lo], a[--j]));
            if(i >= j) {
                break;
            }
            exch(a, i, j);
        }
        exch(a, lo, j);
        return j;
    }

    private void exch(int[] a, int i, int j) {
        final int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

    private boolean less(int v, int w) {
        return v < w;
    }

图片.png

可以看到由于最坏情况的存在,所以其实效率并不理想

4改进快排

我们考虑改进上面的快排算法,我们知道当数据有序时,会产生最坏情况,那么我们就随机化输入的数据,这样可以尽量避免最坏情况的发生。

public class Solution {
    public int findKthLargest(int[] nums, int k) {

        shuffle(nums);
        k = nums.length - k;
        int lo = 0;
        int hi = nums.length - 1;
        while (lo < hi) {
            final int j = partition(nums, lo, hi);
            if(j < k) {
                lo = j + 1;
            } else if (j > k) {
                hi = j - 1;
            } else {
                break;
            }
        }
        return nums[k];
    }

private void shuffle(int a[]) {

        final Random random = new Random();
        for(int ind = 1; ind < a.length; ind++) {
            final int r = random.nextInt(ind + 1);
            exch(a, ind, r);
        }
    }

    private int partition(int[] a, int lo, int hi) {

        int i = lo;
        int j = hi + 1;
        while(true) {
            while(i < hi && less(a[++i], a[lo]));
            while(j > lo && less(a[lo], a[--j]));
            if(i >= j) {
                break;
            }
            exch(a, i, j);
        }
        exch(a, lo, j);
        return j;
    }

    private void exch(int[] a, int i, int j) {
        final int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

    private boolean less(int v, int w) {
        return v < w;
    }
}

可以看到算法果然改进了不少

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LintCode整数排序题目分析解答选择排序插入排序小结

    Given an integer array, sort it in ascending order. Use selection sort, bubble s...

    desperate633
  • [编程题] 赶去公司代码

    终于到周末啦!小易走在市区的街道上准备找朋友聚会,突然服务器发来警报,小易需要立即回公司修复这个紧急bug。假设市区是一个无限大的区域,每条街道假设坐标是(X,...

    desperate633
  • LeetCode 75. Sort Colors题目分析

    给定一个包含红,白,蓝且长度为 n 的数组,将数组元素进行分类使相同颜色的元素相邻,并按照红、白、蓝的顺序进行排序。 我们可以使用整数 0,1 和 2 分别代...

    desperate633
  • P3809 【模版】后缀排序

    题目背景 这是一道模版题。 题目描述 读入一个长度为 nn 的由大小写英文字母或数字组成的字符串,请把这个字符串的所有非空后缀按字典序从小到大排序,然后按顺序输...

    attack
  • 蓝桥杯--算法入门级题目及答案解析

    写在最前面: 本文中会出现大量的请查阅.请自学什么的,不是我不讲,本文是面向算法初学者和蓝桥杯的文章,如果真的想看进阶算法的也不会来看这些题目,所以不要介意,...

    风骨散人Chiam
  • BZOJ4698: Sdoi2008 Sandy的卡片(二分 hash)

    attack
  • LeetCode第五天

    leetcode 第五天 2018年1月6日 22.(566) Reshape the Matrix ? ? JAVA class Solution { ...

    郭耀华
  • 算法原理系列:木桶排序

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 高仿京东金融的数值滚动尺

    以前博客讲的大部分都是静态的自定义View的编写,其实无非就是“画画”画出一个好看的效果,而这篇博客写的是写一个动态的自定义控价,这里不仅需要"画",还要各种事...

    HelloJack
  • 洛谷P4054 [JSOI2009]计数问题(二维树状数组)

    attack

扫码关注云+社区

领取腾讯云代金券