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 条评论
登录 后参与评论

相关文章

来自专栏chenjx85的技术专栏

leetcode-605-Can Place Flowers

10830
来自专栏积累沉淀

各种排序算法的总结和比较

1 快速排序(QuickSort) 快速排序是一个就地排序,分而治之,大规模递归的算法。从本质上来说,它是归并排序的就地版本。快速排序可以由下面四步组成。...

20160
来自专栏从流域到海域

Python 函数

Python的函数与其他语言的函数概念上是一致的,只是形式上有所不同。在面向过程的编程语言中(C语言),函数是代码的基本组成形式,是功能的基本模块;在面向...

22270
来自专栏杨建荣的学习笔记

重温快速排序(r4笔记第73天)

说起排序,总是会想起大名鼎鼎的快速排序,等自己再次翻开快速排序时,感觉是很陌生的,从这个对比也能看出自己确实是已经忘记了曾经重要的日子。 快速排序使用了分治思想...

36470
来自专栏落影的专栏

程序员进阶之算法练习(十六)

前言 正文6道题目来自leetcode––为求职为生的编程网站,目的是工作闲暇之时锤炼代码功底。 没有捷径,但手熟尔; 一步领先,步步领先。 正文 5. L...

40350
来自专栏互联网杂技

各种排序算法总结

排序算法是最基本最常用的算法,不同的排序算法在不同的场景或应用中会有不同的表现,我们需要对各种排序算法熟练才能将它们应用到实际当中,才能更好地发挥它们的优势。今...

36450
来自专栏轮子工厂

八大排序算法稳定性分析,原来稳定性是这个意思...

2、在一趟选择中,如果当前元素比一个元素小,而该小的元素又出现在一个和当前元素相等的元素后面,那么交换后稳定性就被破坏了;

27260
来自专栏用户画像

排序算法 归纳总结

一、直接插入排序、冒泡排序和简单选择排序是最基本的排序方法,它们主要用于元素个数n(n<10000)不是很大的情形。

9020
来自专栏云霄雨霁

字符串排序----排序算法的选择

25800
来自专栏chenjx85的技术专栏

leetcode-561-Array Partition I

20170

扫码关注云+社区

领取腾讯云代金券