LeetCode

要求:

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

使用快排进行解决。

 1 class Solution {
 2     func findKthLargest(_ nums: [Int], _ k: Int) -> Int {
 3         
 4         let quickSortResult = quickSort(nums, 0, nums.count - 1)
 5         let resultNums = quickSortResult.0
 6         let keyIndex = quickSortResult.1
 7         
 8         if keyIndex + 1 == k {
 9             
10         }else if keyIndex + 1 > k {
11             return findKthLargest(Array(resultNums[0..<keyIndex]), k)
12         }else {
13             let index = resultNums.index(after: keyIndex)
14             let endIndex = resultNums.endIndex
15             return findKthLargest(Array(resultNums[index..<endIndex]), k - keyIndex - 1)
16         }
17         return resultNums[keyIndex]
18     }
19     
20     private
21     func quickSort(_ nums: [Int], _ left: Int, _ right: Int) -> ([Int], Int) {
22         var numsArray = nums
23         var i = left
24         var j = right
25         let key = numsArray[i]
26         
27         while i != j {
28             while j > i && numsArray[j] <= key {
29                 j -= 1
30             }
31             numsArray.swapAt(i, j)
32             
33             while j > i && numsArray[i] >= key {
34                 i += 1
35             }
36             numsArray.swapAt(i, j)
37         }
38         numsArray[i] = key
39         return (numsArray, i)
40     }
41 }