题目

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

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

示例 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 <= 104

-104 <= nums[i] <= 104

注意：本题与主站 215 题相同：

解题思路分析

1、排序；时间复杂度O(nlog(n))，空间复杂度O(1)

func findKthLargest(nums []int, k int) int {
   sort.Ints(nums)
   return nums[len(nums)-k]
}

2、堆排序；时间复杂度O(nlog(n))，空间复杂度O(log(n))

func findKthLargest(nums []int, k int) int {
   heapSize := len(nums)
   buildMaxHeap(nums, heapSize)
   for i := len(nums) - 1; i >= len(nums)-k+1; i-- {
      nums[0], nums[i] = nums[i], nums[0]
      heapSize--
      maxHeapify(nums, 0, heapSize)
   }
   return nums[0]
}

func buildMaxHeap(a []int, heapSize int) {
   for i := heapSize / 2; i >= 0; i-- {
      maxHeapify(a, i, heapSize)
   }
}

func maxHeapify(a []int, i, heapSize int) {
   l, r, largest := i*2+1, i*2+2, i
   if l < heapSize && a[l] > a[largest] {
      largest = l
   }
   if r < heapSize && a[r] > a[largest] {
      largest = r
   }
   if largest != i {
      a[i], a[largest] = a[largest], a[i]
      maxHeapify(a, largest, heapSize)
   }
}

3、快排；时间复杂度O(n)，空间复杂度O(log(n))

func findKthLargest(nums []int, k int) int {
   return findK(nums, 0, len(nums)-1, k)
}

func findK(nums []int, start, end int, k int) int {
   if start >= end {
      return nums[end]
   }
   index := partition(nums, start, end)
   if index+1 == k {
      return nums[index]
   } else if index+1 < k {
      return findK(nums, index+1, end, k)
   }
   return findK(nums, start, index-1, k)
}

func partition(nums []int, start, end int) int {
   temp := nums[end]
   i := start
   for j := start; j < end; j++ {
      if nums[j] > temp {
         if i != j {
            nums[i], nums[j] = nums[j], nums[i]
         }
         i++
      }
   }
   nums[i], nums[end] = nums[end], nums[i]
   return i
}

总结

Medium题目，题目同leetcode 215.数组中的第K个最大元素