题目：

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

请留神，你须要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

  • 1 <= k <= nums.length <= 104
  • -104 <= nums[i] <= 104

本算法题目有两种比拟好的办法，别离为应用小顶堆和应用疾速抉择。

题解一：

首先咱们应用小顶堆的办法求解，先贴代码（Go语言）：

type IntHeap []intfunc (h IntHeap) Len() int           { return len(h) }func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }func (h IntHeap) Top() int {   return h[0]}func (h *IntHeap) Push(x interface{}) {   // Push and Pop use pointer receivers because they modify the slice's length,   // not just its contents.   *h = append(*h, x.(int))}func (h *IntHeap) Pop() interface{} {   old := *h   n := len(old)   x := old[n-1]   *h = old[0 : n-1]   return x}func findKthLargest(nums []int, k int) int {   h := &IntHeap{}   heap.Init(h)   for _, num := range nums {      if h.Len() < k {         heap.Push(h, num)      } else if (*h)[0] < num {         heap.Pop(h)         heap.Push(h, num)      }   }   return heap.Pop(h).(int)}

首先咱们确定循环不变量：h中始终存储了最多k个数组元素，且是目前遍历过的最大的k个元素，且其中最小的元素为(*h)[0]。

h是一个小顶堆，则h可能保障，退出其中的元素的最小的元素为(*h)[0]。（小顶堆的概念可自行Google）

初始化： h中没有元素，不变式成立。

放弃： 在迭代过程中，依据h的元素数量，分为如下两种状况：

  • 如果h中元素的个数小于k，间接将本次迭代的数组元素num退出到h中。
  • 如果h中元素的个数大于等于k，则须要比拟以后h中，最小的元素是否大于num，若是，疏忽num的解决，否则，将其替换为num。
    以上两种状况的后果均能够保障不变式成立。

终止： nums中的所有元素均被遍历后算法终止，不变式成立。

最终h中的最小元素(*h)[0]即为数组nums的第K个最大元素。

复杂度剖析：

工夫复杂度：O(nlogn)，建堆的工夫代价是 O(n)，删除的总代价是O(klogn)，因为 k < nk < n，故渐进工夫简单为O(n + klogn) = O(nlogn)。

空间复杂度：O(logn)，即递归应用栈空间的空间代价。

题解二：

咱们同样能够应用疾速抉择的办法求解，先贴代码（Go语言）：

func findKthLargest(nums []int, k int) int {   rand.Seed(time.Now().UnixNano())   return quickSelect(nums, 0, len(nums)-1, k)}func quickSelect(nums []int, l int, r int, k int) int {   m := randomPartition(nums, l, r)   if r-m+1 == k {      return nums[m]   } else if r-m+1 > k {      return quickSelect(nums, m+1, r, k)   } else {      return quickSelect(nums, l, m-1, k-(r-m+1))   }}func randomPartition(nums []int, l, r int) int {   i := rand.Int()%(r-l+1) + l   nums[i], nums[r] = nums[r], nums[i]   return partition(nums, l, r)}func partition(nums []int, l int, r int) int {   key := nums[r]   //all in [l,i) < key   //all in [i,j] > key   i := l   j := l   for j < r {      if nums[j] < key {         nums[i], nums[j] = nums[j], nums[i]         i++      }      j++   }   nums[i], nums[r] = nums[r], nums[i]   return i}

疾速抉择与疾速排序很相似，应用了雷同的分治思维，（疾速排序算法可参考这篇文章）将疾速排序的解决阶段稍加批改即可。同时咱们这里的疾速抉择算法应用了随机采样的办法，进步了算法的性能。

复杂度剖析：

工夫复杂度：O(n)，如上文所述，证实过程能够参考「《算法导论》9.2：冀望为线性的抉择算法」。

空间复杂度：O(log n)，递归应用栈空间的空间代价的冀望为 O(logn)。

两种解法的比照：

  • 疾速抉择算法工夫复杂度更低，且不须要额定的存储空间。然而必须事后晓得数组的总长度，所以适宜对定长数组的计算。
  • 堆须要额定的k个存储空间，且算法工夫复杂度绝对高一些。然而不须要事后晓得待处理数组的规模，所以适宜对流数据进行解决。