消零燕归来算法刷题

LeetCode刷题-第k大的数

2021-07-29  本文已影响0人  小鲨鱼FF

前言说明

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

题目连接

第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%的用户。

运行结果

关注更多

更多链接:更多链接

上一篇下一篇

猜你喜欢

热点阅读