[Swift]LeetCode215. 数组中的第K个最大元素 | Kth Largest Element in an Array

概述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: and k = 2Output: 5[3,2,1,5,6,4] Exam

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: and k = 2Output: 5[3,2,1,5,6,4]

Example 2:

input: and k = 4Output: 4[3,3,4,6]

Note: 
You may assume k is always valID,1 ≤ k ≤ array‘s length.

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

示例 1:

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

示例 2:

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

说明:

你可以假设 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,i)11         }12         return 013     }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,i)20         }21     }22     //建最大堆23     func buildMaxhead(_ nums:inout [Int]) {24         for i in (0...nums.count/2).reversed() {25             headify(&nums,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 = leftChild35         }36         if rightChild < length && nums[rightChild] > nums[largertIndex] {37             largertIndex = rightChild38         }39         //如果交换了40         if largertIndex != index {41             swap(&nums,largertIndex,index)//交换节点值42             headify(&nums,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] = temp49     }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 - pivot10         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,pivot - 1,k)17     }18 19     func partition(_ nums: inout [Int],_ end: Int) -> Int {20         guard start < end else {21             return start22         }23         let pivot = Int.random(in: start...end)24         nums.swapAt(pivot,end)25         var index = start26         for i in start..<end where nums[i] < nums[end] {27             nums.swapAt(i,index)28             index += 129         }30         nums.swapAt(index,end)31         return index32     }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,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],end: Int) -> Int {15         guard start < end else { return start }16         17         var i = start18         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 += 126             }27         }28         29         (arr[i],arr[i])30         return i31     }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 = 011         while i < k - 1 {12             swap(&nums,heapSize - 1)13             heapSize -= 114             maxHeapAdjust(&nums,0)15             i += 116         }17         return nums[0]18     }19     20     func buildMaxHeap(_ nums: inout [Int]) {21         heapSize = nums.count22         var i = heapSize >> 1 - 123         while i >= 0 {24             maxHeapAdjust(&nums,i)25             i -= 126         }27     }28     29     func maxHeapAdjust(_ nums: inout [Int],_ index: Int) {30         var largest = index31         var l = index << 1 + 132         var r = index << 1 + 233         if l < heapSize && nums[l] > nums[largest] {34             largest = l35         }36         if r < heapSize && nums[r] > nums[largest] {37             largest = r38         }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] = temp49     }50 }

总结

以上是内存溢出为你收集整理的[Swift]LeetCode215. 数组中的第K个最大元素 | Kth Largest Element in an Array全部内容，希望文章能够帮你解决[Swift]LeetCode215. 数组中的第K个最大元素 | Kth Largest Element in an Array所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。