每日一题 --- 数组中的第 K 个最大元素[力扣][Go]

数组中的第 K 个最大元素

题目：数组中的第 K 个最大元素

给定整数数组 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

方法一：

使用快速排序，排好序后找到第K大的元素。

func findKthLargest(nums []int, k int) int {
   if len(nums) < k {
      return -1
   }
   qSort(nums)
   return nums[len(nums)-k]
}

func qSort(nums []int) {
   quickSort(nums, 0, len(nums)-1)
}

// 快速排序算法
func quickSort(nums []int, min, max int) {
   if min < max {
      pos := partition(nums, min, max)
      quickSort(nums, min, pos-1)
      quickSort(nums, pos+1, max)
   }
}

func partition(nums []int, l, r int) int {
   base := nums[l]
   for l < r {
      for l < r && nums[r] >= base {
         r--
      }
      nums[l] = nums[r]
      for l < r && nums[l] <= base {
         l++
      }
      nums[r] = nums[l]
   }
   nums[l] = base
   return l
}

方法二：

使用堆排序，排好序后，调整K次大根堆，然后取出元素值

func findKthLargest(nums []int, k int) int {
   // 实现卫兵
   nums = append([]int{0}, nums...)
   Len := len(nums)
   buildMaxHeap(nums, Len-1)
   for i := Len - 1; i >= Len-k; i-- {
      nums[1], nums[i] = nums[i], nums[1]
      maxHeapAdjust(nums, 1, i-1)
   }
   return nums[Len-k]
}

// 建堆
func buildMaxHeap(nums []int, len int) {
   for i := len / 2; i > 0; i-- {
      maxHeapAdjust(nums, i, len)
   }
}

// 调整堆, k为根元素，从k开始往下调整
func maxHeapAdjust(nums []int, k, len int) {
   nums[0] = nums[k]
   for i := 2 * k; i <= len; i *= 2 {
      if i < len && nums[i] < nums[i+1] {
         i++
      }
      if nums[i] <= nums[0] {
         break
      } else {
         nums[k] = nums[i]
         k = i
      }
   }
   nums[k] = nums[0]
}

方法一和方法二都是采取，先排序再取值的办法。时间复杂度为O(n*log n)。

其实我们可以改进下方法一：利用分治思想将时间复杂度期望降至O(1)。

具体思想讲解：4.3分治寻找第k小元素_哔哩哔哩_bilibili

方法三：

分治法，与上面思想不同的是，我们不执着于找中位数，而是采用随机分治，当随机到的基数正好为第K大时，直接返回。详细讲解参考力扣题解部分。

func findKthLargest(nums []int, k int) int {
   if len(nums) < k {
      return -1
   }
   return qSort(nums, len(nums)-k)
}

func qSort(nums []int, index int) int {
   rand.Seed(time.Now().UnixNano())
   return quickSort(nums, 0, len(nums)-1, index)
}

// 快速排序算法
func quickSort(nums []int, min, max, index int) int {
   randN := rand.Int()%(max-min+1) + min
   pos := partition(nums, min, max, randN)
   if pos == index {
      return nums[pos]
   } else if pos < index {
      return quickSort(nums, pos+1, max, index)
   } else {
      return quickSort(nums, min, pos-1, index)
   }

}

func partition(nums []int, l, r, random int) int {
   nums[random], nums[l] = nums[l], nums[random]
   base := nums[l]
   for l < r {
      for l < r && nums[r] >= base {
         r--
      }
      nums[l] = nums[r]
      for l < r && nums[l] <= base {
         l++
      }
      nums[r] = nums[l]
   }
   nums[l] = base
   return l
}

理论上期望时间复杂度为O(n)，求证：算法导论中文版.pdf · FaithLight/books - Gitee.com，定位：《算法导论》9.2