LeetCode-215.数组中的第K个最大元素

发表于 分类于

题目描述

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

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

示例

1
2
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
1
2
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

提示：

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

题解

利用快排的思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
func findKthLargest(_ nums: [Int], _ k: Int) -> Int {
  var numbers = nums
  let targetIndex = numbers.count - k
  var left = 0
  var right = numbers.count - 1
  while true {
    let index = patitation(&numbers, left, right)
    if index == targetIndex {
      return nums[index]
    } else if index < targetIndex {
      left = index + 1
    } else {
      right = index - 1
    }
  }
}

func patitation(_ nums: inout [Int], _ left: Int, _ right: Int) -> Int {
  guard left < right else { return left }
  var begin = left
  var end = right
  let povit = nums[begin]
  while begin < end {
    while begin < end && nums[end] >= povit {
      end -= 1
    }
    if begin < end {
      nums[begin] = nums[end]
      begin += 1
    }
    while begin < end && nums[begin] < povit {
      begin += 1
    }
    if begin < end {
      nums[end] = nums[begin]
      end -= 1
    }
  }
  nums[begin] = povit
  return begin
}