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

题目描述

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

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

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

示例 1:

输入: [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⁵
-10⁴ <= nums[i] <= 10⁴

解法一：快速排序思想

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41


func findKthLargest(nums []int, k int) int {
    var partition func(l, r int) int
    var randomPartition func(l, r int) int
    var quickSelect func(l, r, index int) int

    partition = func(l, r int) int {
        if l >= r {
            return l
        }
        p, idx := nums[l], l+1
        for i := l + 1; i <= r; i++ {
            if nums[i] <= p {
                nums[idx], nums[i] = nums[i], nums[idx]
                idx++
            }
        }
        nums[idx-1], nums[l] = nums[l], nums[idx-1]
        return idx - 1
    }

    randomPartition = func(l, r int) int {
        i := rand.Intn(r-l+1) + l
        nums[l], nums[i] = nums[i], nums[l]
        return partition(l, r)
    }

    quickSelect = func(l, r, index int) int {
        p := randomPartition(l, r)
        if p == index {
            return nums[p]
        } else if p > index {
            return quickSelect(0, p-1, index)
        } else {
            // p < index
            return quickSelect(p+1, r, index)
        }
    }

    rand.New(rand.NewSource(time.Now().UnixNano()))
    return quickSelect(0, len(nums)-1, len(nums)-k)
}