题目
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.
题意
求无序数组中的第k大元素
例子
Input: [3,2,1,5,6,4] and k = 2
Output: 5
题解
利用快排的思想，选取一个元素（一般是第一个），然后将大于该元素的值放在右边，小于放左边（这是从小到大递增，大到小递增就放过来），然后确定该元素的位置，如果该位置恰好为第k个，就可以返回了。
### 代码
func findKthLargest(nums []int, k int) int {
return QuitFind(nums,0,len(nums)-1,k)
}
func QuitFind(nums []int,start,end,k int)int{
if start>end{
return -1
}
mid := quitFind(nums,start,end)
kth := len(nums)-mid
if k==kth{
return nums[mid]
}
ql := QuitFind(nums,start,mid-1,k)
if ql!=-1{
return ql
}
qr := QuitFind(nums,mid+1,end,k)
if qr!=-1{
return qr
}
return -1
}
func quitFind(nums []int,start,end int)int{
temp := nums[start]
for start<end{
for nums[end]>temp&&start<end{
end--
}
nums[start]=nums[end]
for nums[start]<=temp && start<end{
start++
}
nums[end]=nums[start]
}
nums[start]=temp
return start
}
总结
遇见过类型的题了，这道题很简单。使用go原生的排序算法先排序在翻转竟然比手写一个快排思路的方法还要快。。。而且只需要两行代码
func findKthLargest(nums []int, k int) int {
sort.Sort(sort.Reverse(sort.IntSlice(nums)))
return nums[k-1]
}
