[Swift]LeetCode215. 数组中的第K个最大元素 | Kth Largest Element in an Array
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10197956.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
Example 1:
Input: [3,2,1,5,6,4] and k = 2
Output: 5
Example 2:
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.
在未排序的数组中找到第 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说明:
你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
24ms
1 class Solution {
2 func findKthLargest(_ nums: [Int], _ k: Int) -> Int {
3 return nums.sorted(by: >)[k - 1]
4 }
5 }56ms
1 class Solution {
2 func findKthLargest(_ nums: [Int], _ k: Int) -> Int {
3 var newNums = nums
4 buildMaxHead(&newNums)//建最大堆
5 for i in ((newNums.count - k - 1)..<newNums.count).reversed() {
6 swap(&newNums, 0, i)
7 if i == newNums.count - k {
8 return newNums[i]
9 }
10 headify(&newNums, 0, i)
11 }
12 return 0
13 }
14 //MARK: 堆排序
15 func headSort(_ nums:inout [Int]) {
16 buildMaxHead(&nums)
17 for i in (1..<nums.count).reversed() {
18 swap(&nums, i, 0)
19 headify(&nums, 0, i)
20 }
21 }
22 //建最大堆
23 func buildMaxHead(_ nums:inout [Int]) {
24 for i in (0...nums.count/2).reversed() {
25 headify(&nums, i,nums.count)
26 }
27 }
28 //堆调整
29 func headify(_ nums:inout [Int], _ index: Int, _ length: Int) {
30 let leftChild = index * 2 + 1 // index节点的左孩子节点
31 let rightChild = index * 2 + 2 //index节点的右孩子节点
32 var largertIndex = index //节点与左右孩子的最大值
33 if leftChild < length && nums[leftChild] > nums[largertIndex] {
34 largertIndex = leftChild
35 }
36 if rightChild < length && nums[rightChild] > nums[largertIndex] {
37 largertIndex = rightChild
38 }
39 //如果交换了
40 if largertIndex != index {
41 swap(&nums, largertIndex, index)//交换节点值
42 headify(&nums, largertIndex,length)//调整变动的节点
43 }
44 }
45 func swap(_ nums:inout [Int],_ i:Int,_ j: Int) {
46 let temp = nums[i]
47 nums[i] = nums[j]
48 nums[j] = temp
49 }
50 }56ms
1 class Solution {
2 func findKthLargest(_ nums: [Int], _ k: Int) -> Int {
3 var nums = nums
4 return find(&nums, 0, nums.count - 1, k)
5 }
6
7 func find(_ nums: inout [Int], _ start: Int, _ end: Int, _ k: Int) -> Int {
8 let pivot = partition(&nums, start, end)
9 let j = nums.count - pivot
10 if j > k {
11 return find(&nums, pivot + 1, end, k)
12 }
13 if j == k {
14 return nums[pivot]
15 }
16 return find(&nums, start, pivot - 1, k)
17 }
18
19 func partition(_ nums: inout [Int], _ start: Int, _ end: Int) -> Int {
20 guard start < end else {
21 return start
22 }
23 let pivot = Int.random(in: start...end)
24 nums.swapAt(pivot, end)
25 var index = start
26 for i in start..<end where nums[i] < nums[end] {
27 nums.swapAt(i, index)
28 index += 1
29 }
30 nums.swapAt(index, end)
31 return index
32 }
33 }60ms
1 class Solution {
2 func findKthLargest(_ nums: [Int], _ k: Int) -> Int {
3 var arr = nums
4 return quickselect(arr: &arr, start: 0, end: arr.count - 1, k: arr.count - k)
5 }
6
7 private func quickselect(arr: inout[Int], start: Int, end: Int, k: Int) -> Int {
8 let pivot = partition(arr: &arr, start: start, end: end)
9 if pivot > k { return quickselect(arr: &arr, start: start, end: pivot - 1, k: k) }
10 if pivot == k { return arr[pivot] }
11 return quickselect(arr: &arr, start: pivot + 1, end: end, k: k)
12 }
13
14 private func partition(arr: inout[Int], start: Int, end: Int) -> Int {
15 guard start < end else { return start }
16
17 var i = start
18 let pivotIndex = Int.random(in: start ... end)
19 let pivot = arr[pivotIndex]
20 (arr[pivotIndex], arr[end]) = (arr[end], arr[pivotIndex])
21
22 for j in start ..< end {
23 if arr[j] < pivot {
24 (arr[i], arr[j]) = (arr[j], arr[i])
25 i += 1
26 }
27 }
28
29 (arr[i], arr[end]) = (arr[end], arr[i])
30 return i
31 }
32
33 }84ms
1 class Solution {
2 private var heapSize = 0
3
4 func findKthLargest(_ nums: [Int], _ k: Int) -> Int {
5 guard nums.count > 0 else {
6 return 0
7 }
8 var nums = nums
9 buildMaxHeap(&nums)
10 var i = 0
11 while i < k - 1 {
12 swap(&nums, 0, heapSize - 1)
13 heapSize -= 1
14 maxHeapAdjust(&nums, 0)
15 i += 1
16 }
17 return nums[0]
18 }
19
20 func buildMaxHeap(_ nums: inout [Int]) {
21 heapSize = nums.count
22 var i = heapSize >> 1 - 1
23 while i >= 0 {
24 maxHeapAdjust(&nums, i)
25 i -= 1
26 }
27 }
28
29 func maxHeapAdjust(_ nums: inout [Int],_ index: Int) {
30 var largest = index
31 var l = index << 1 + 1
32 var r = index << 1 + 2
33 if l < heapSize && nums[l] > nums[largest] {
34 largest = l
35 }
36 if r < heapSize && nums[r] > nums[largest] {
37 largest = r
38 }
39 if largest != index {
40 swap(&nums, largest, index)
41 maxHeapAdjust(&nums, largest)
42 }
43 }
44
45 func swap(_ nums: inout [Int], _ i: Int,_ j: Int) {
46 let temp = nums[i]
47 nums[i] = nums[j]
48 nums[j] = temp
49 }
50 }