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

## Link

{% embed url="<https://leetcode.cn/problems/kth-largest-element-in-an-array/>" %}

## Problem

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

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

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

示例 1：

{% code overflow="wrap" %}

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

{% endcode %}

示例2：

{% code overflow="wrap" %}

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

{% endcode %}

提示：

* `1 <= k <= nums.length <= 105`
* `-104 <= nums[i] <= 104`

## Solution

{% tabs %}
{% tab title="Go" %}

```go
func findKthLargest(nums []int, k int) int {
    sink := func(heap []int, i int, end int) {
        for j := i * 2 + 1; j <= end; j = j * 2 + 1 {
            if j < end && heap[j+1] < heap[j] {
                j++
            }
            if heap[i] < heap[j] {
                break
            }
            heap[i], heap[j] = heap[j], heap[i]
            i = j
        }
    }

    //从下标 k-1 往前建立小顶堆
    for i := (k-1)>>1; i >=0; i-- {
        sink(nums, i, k-1)
    }

    //从下标k开始向堆中插入元素
    for i := k; i < len(nums); i++ {
        if nums[i] > nums[0] {
            nums[0], nums[i] = nums[i], nums[0]
            sink(nums, 0, k-1)
        }
    }

    return nums[0]
}
```

{% endtab %}

{% tab title="C++" %}

```cpp
```

{% endtab %}
{% endtabs %}