LeetCode刷题-第k大的数

前言说明

算法学习，日常刷题记录。

题目连接

第k大的数

额外说明

之前，我发了一道求第三大的数的题，如下：

第三大的数

里面说到直接三次遍历解决，时间复杂度为O(3n)，常数项可以去掉，O(3n)=O(n)，所以时间复杂度为O(n)。

但是我的朋友看了后突然问我，如果是第k大的数呢？怎么办？

我又查找了下LeetCode上的相关题，果然就有一道第k大的数的，下面就来聊聊怎么求第k大的数。

题目内容

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第k个最大的元素，而不是第 k 个不同的元素。

示例1:

输入: [3,2,1,5,6,4] 和 k = 2

输出: 5

示例2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4

输出: 4

说明：

你可以假设k总是有效的，且1 ≤ k ≤数组的长度。

分析过程

其实思路很简单，先对数组排序，排好序后，直接拿出倒数第k个数即可。

排序时直接调用系统提供的sort方法排序，sort方法排序使用的是快排，效率是比较好的。

排序好数组后，取倒数第k个数，因为前面排序后是从小到大的，这里通过数组长度-k得到第k个数的索引。

解答代码

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 对数组排序，用系统提供的sort方法排序
        Arrays.sort(nums);
        // 取倒数第k个数，因为前面排序后是从小到大的，这里通过数组长度-k得到第k个数的索引
        return nums[nums.length - k];
    }
}

提交结果

执行用时2ms，时间击败91.13%的用户，内存消耗38.6MB，空间击败71.09%的用户。

运行结果

关注更多

更多链接：更多链接