分析：

这道题本质是一个排序算法，最简单的方法就是把数组 nums 由小到大排好序，想要找到第 K 个最大的元素，那么直接返回 nums[len(nums) – k] 即可。关键点是必须设计实现时间复杂度为 O(n) 的算法。

上图链接来源https://blog.csdn.net/qq_34411783/article/details/97611152

从十大排序算法中可以很直观地得到，想要实现 O(n) 甚至更小的时间复杂度可选的算法有堆排序O(nlogn)、快速排序O(nlogn)、归并排序O(nlogn)。

此题选择堆排序来求解。

代码：

func findKthLargest(nums []int, k int) int {
    // 建堆->交换堆顶元素和末尾元素->删除元素->维护堆
    // 建堆是把所有非叶子节点都按照堆的规则排序(从倒数第一个非叶子节点开始一直到根节点)
    // 建堆。在一开始建堆时，是从最后一个非叶子节点开始按照自下而上，自左向右进行调整的。
    for i := len(nums) / 2 - 1; i >= 0; i-- {
        adjustHeap(nums, i, len(nums))
    }

    // 交换、删除、维护
    for j := len(nums) - 1; j > 0; j-- {
        // 交换堆顶元素和数组末尾元素
        swap(nums, 0, j)
        // 交换元素后，数组的最后一个元素无需再考虑排序问题，对剩下的元素维护堆
        // 后续维护堆的时候是从索引为0的根节点开始按照自上而下，自左向右进行调整的。
        adjustHeap(nums, 0, j)
    } 

    // 返回结果
    return nums[len(nums) - k]
}

func adjustHeap(nums []int, i int, length int) {
    // 先把当前元素取出来，因为当前元素可能一直要移动
    temp := nums[i]
    // 从上述建堆完成以及第一次交换结束之后，实质上 i=0,即从根节点开始，所以下述讲解
    // 按照i=0进行讲述
    // 传入的节点索引为i,那么该节点的左节点索引为k = 2*i+1是很好理解的，从左节点开始遍历
    // 那么右节点索引就是 k+1
    for k := 2 * i + 1; k < length; k = 2 * k + 1 {
        // 先比较当前节点 i 的两个子节点 k 和 k + 1，取其大(即k指向最大的节点)
        if k + 1 < length && nums[k] < nums[k + 1] {
            k++
        }
        // 如果发现子节点更大，则进行值的交换
        if nums[k] > temp {
            swap(nums, i, k)
            // 重要的一步，要保证三个节点调整之后，会不会对原来的子树造成影响
            // 所以，循环对子节点所在的树继续进行判断，因为k是子节点，i是父节点
            // 把 k 赋值给 i,下一轮判断就是在子节点所在的树进行判断
            i = k
            // 如果不用交换，那么就直接终止循环了
        } else {
            break
        }
    }
}

// swap 交换数组元素
func swap(nums []int, i int, k int) {
    temp := nums[i]
    nums[i] = nums[k]
    nums[k] = temp
}

解析：

堆排序的设计思想与求解见链接https://blog.csdn.net/qq_34411783/article/details/97611152

堆排序分为大顶堆和小顶堆，下面步骤以大顶堆为例。

步骤一：建堆。将给定的无序数组构造成一个大顶堆。

• a.从最后一个非叶子节点开始，对于二叉树来说，最后一个非叶子节点索引为 len(nums) / 2 – 1，然后从左到右，从下向上进行调整。
• b.以该非叶子节点和其左右子节点，共三个节点之间进行比较大小，将最大的节点交换为父节点，这里要注意，子节点和父节点进行交换后，必须考虑新的子节点是否会对原来树造成影响，即时刻要维护堆。
• c.寻找第二个非叶子节点，继续上述步骤b，一直遍历到树的根节点才算建堆结束。

for i := len(nums) / 2 - 1; i >= 0; i-- {
        adjustHeap(nums, i, len(nums))
}

这部分代码的 for 循环就是从最后一个非叶子节点不断遍历直到根节点，按照节点大小规则进行调整直至建堆完成。

步骤二：交换，删除，维护。

• a.交换是指将堆顶元素和数组末尾元素进行交换，此时的数组末尾元素就是最大的元素，然后将其删除，剩下的 len(nums) – 1 个元素再进行堆的维护。当然，这时再调用 adjustHeap 方法时传入的节点就是根节点，从上向下，从左向右开始调整。因为只有根节点变动了，所以要从根节点调整。
• b.不断地进行步骤a，直到数组剩一个元素时，该元素毫无疑问也是最小的。

经过步骤一和步骤二，一个无序数组就变成了一个升序数组。

代码的详细解析见上述代码注释部分。

复杂度分析：

时间复杂度：O(nlogn)，十大排序算法没什么好说的。

空间复杂度：O(1)。

这里引申一下堆排序的应用场景。

有时候面试官会提出在非常大的数据量面前，用什么样的排序算法性能会更好？

堆排序就适合数据量非常大的场合。因为堆排序不需要大量的递归或引入其他的暂存数组。这对于数据量非常巨大的序列是非常合适的。比如超过数百万条记录，虽然快速排序、归并排序与堆排序的时间复杂度同为O(nlogn)，但是堆排序的空间复杂度为O(1)，而快速排序的空间复杂度为O(nlogn)，归并排序的空间复杂度为O(n)，在数据量非常大的时候，可能会发生堆栈溢出错误。所以堆排序更适用于数据量非常的场景来对数据进行排序。