題目：
在未排序的數組中找到第
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 ≤ 數組的長度。
解題思路：先倒序排序，然後第K個數。
func findKthLargest(nums []int, k int) int {
sortData(nums)
return nums[k-1]
}
func sortData(nums []int) {
if len(nums)<=1{
return
}
target,left,right:=0,1,len(nums)-1
for left<=right{
if nums[left]>nums[target]{
nums[left],nums[target]=nums[target],nums[left]
left++
target++
}else{
nums[left],nums[right]=nums[right],nums[left]
right--
}
}
sortData(nums[:target])
sortData(nums[target+1:])
}
執行用時40ms，幹掉了13%golang提交。
優化：根據快速排序算法改動，不進行完全排序，根據標記位來判斷數據位的位置，只比較第K個數所在的一側，大幅度減少比較運算。
func findKthLargest(nums []int, k int) int {
return sortData(nums,k)
}
func sortData(nums []int,k int) int{
if len(nums)==0{
return -1
}
if len(nums)==1{
return nums[0]
}
target,left,right:=0,1,len(nums)-1
for left<=right{
if nums[left]>nums[target]{
nums[left],nums[target]=nums[target],nums[left]
left++
target++
}else{
nums[left],nums[right]=nums[right],nums[left]
right--
}
}
if target == k-1{
return nums[target]
}else if target >k-1{
return sortData(nums[:target],k)
}else{
return sortData(nums[target+1:],k-target-1)
}
}
執行用時20ms，幹掉了30%golang提交。
使用堆解決，適合大量數據。
建立大頂堆，依次取出k次最大值。
func findKthLargest(nums []int, k int) int {
for i:=0;i
maxHeap(nums[i:])
}
return nums[k-1]
}
//建立大頂堆
func maxHeap(nums []int) {
length:=len(nums)
for i:=length/2-1;i>=0;{
left:=2*i+1
if left
nums[i],nums[left]=nums[left],nums[i]
ll:=left*2+1
rr:=ll+1
if ll
//左子樹交換後，新的左子樹不符合,跳轉到左子樹
i=left
continue
}
}
right:=left+1
if right
nums[i],nums[right]=nums[right],nums[i]
ll:=right*2+1
rr:=ll+1
if ll
//新的右子樹不符合，跳轉到右子樹
i=right
continue
}
}
i--
}
}
執行時間：92ms 貌似效果不太好，複雜度更高了
再次優化：構建小頂堆，維持大小為K的數據，堆頂為結果。（代碼參考自大神的提交）
func findKthLargest(nums []int, k int) int {
m := new(MinHeap)
for i:=0;i
m.push(nums[i])
}
for i:=k;i
if m.peek() < nums[i] {//大於堆頂，取代原來的堆頂數據
m.pop()
m.push(nums[i])
}
}
return m.peek()
}
type MinHeap struct {
arr []int
index int
}
//添加數據自動形成堆
func (this *MinHeap) push(x int) {
if this.index == len(this.arr) {
this.arr = append(this.arr, x)
} else {
this.arr[this.index] = x
}
this.index++
i := this.index-1
for i>0 && this.arr[i] < this.arr[(i-1)/2] {
this.arr[i], this.arr[(i-1)/2] = this.arr[(i-1)/2], this.arr[i]
i = (i-1)/2
}
}
//取出堆頂數據
func (this *MinHeap) pop() int {
this.index--
this.arr[0], this.arr[this.index] = this.arr[this.index], this.arr[0]
for i:=0; 2*i+1
if 2*i+2 < this.index {
if this.arr[2*i+1] < this.arr[2*i+2] && this.arr[i] > this.arr[2*i+1] {
this.arr[i], this.arr[2*i+1] = this.arr[2*i+1], this.arr[i]
i = 2*i+1
} else if this.arr[2*i+1] >= this.arr[2*i+2] && this.arr[i] > this.arr[2*i+2] {
this.arr[i], this.arr[2*i+2] = this.arr[2*i+2], this.arr[i]
i = 2*i+2
} else {
break
}
} else if this.arr[i] > this.arr[2*i+1] {
this.arr[i], this.arr[2*i+1] = this.arr[2*i+1], this.arr[i]
break
} else {
break
}
}
return this.arr[this.index]
}
//獲取堆頂數據
func (this *MinHeap) peek() int {
return this.arr[0]
}
//堆內數據長度
func (this *MinHeap) size() int {
return this.index
}
執行用時4ms，不得不說一句：NB！
關鍵字: findKthLargest 數組 右子樹
