215. 数组中的第K个最大元素

发表于： 分类于：
字数： 386 阅读：≈ 1分钟 浏览： 评论：

https://leetcode.cn/problems/kth-largest-element-in-an-array/

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

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

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

1
2
3
4
5
6

输入: [3,2,1,5,6,4], k = 2
输出: 5
示例 2:

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

提示：

1 <= k <= nums.length <= 10^5

-10^4 <= nums[i] <= 10^4

解题思路

  1. 先考虑一下隐藏条件：
    • 元素可能会重复
  2. 首先想到的，因为 nums 是无序的，因此至少需要遍历一遍，题目要求 O(n) ，则表示需要在遍历的过程中排好序。自然就想到了桶排序。

代码 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func findKthLargest(nums []int, k int) int {
	bucket := make([]int, 20001)
	for _, v := range nums {
		bucket[v+10000]++
	}
	count := len(bucket) - 1
	for {
		if bucket[count] > 0 {
			k = k - bucket[count]
		}
		if k <= 0 {
			return count - 10000
		}
		count--
	}
}

后记

看一眼答案，居然是快排 T_T 。个人其实不喜欢用桶排序，因为受下标约束，不够泛用，并且它的思想很别扭，感觉就像使用redis的时候kv反着存。

但是既然已经写了，并且漂亮地通过了，那么快排兄，下次一定！溜~