topic215

README

数组中的第k个最大元素

1. 题目描述

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

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

2. 示例

示例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 <= 10^4$
• $-10^4 <= nums[i] <= 10^4$

3. 解题

1. 将数组按从大到小排序，然后取第k个值，即为第k个最大元素，时间复杂度为O(nlogn)，空间复杂度为O(1)

2. 使用堆，建堆后取第k个值。

3. 基于快速排序的选择方法
   快速排序每次可确定一个元素的最终位置，即该元素左边的元素小于它，右边的元素大于它，可以利用这点。
   递归的对数组中的元素确认，如果确定了第(len(nums)-k)个元素，则可确定是第k个最大元素。

Documentation

Index

• type IntSlice
  • func (h *IntSlice) Len() int
  • func (h *IntSlice) Less(i, j int) bool
  • func (h *IntSlice) Pop() (v interface{})
  • func (h *IntSlice) Push(v interface{})
  • func (h *IntSlice) Swap(i, j int)

Types

type IntSlice

type IntSlice []int

解法2

func (*IntSlice) Len

func (h *IntSlice) Len() int

func (*IntSlice) Less

func (h *IntSlice) Less(i, j int) bool

func (*IntSlice) Pop

func (h *IntSlice) Pop() (v interface{})

func (*IntSlice) Push

func (h *IntSlice) Push(v interface{})

func (*IntSlice) Swap

func (h *IntSlice) Swap(i, j int)