題目：
在未排序的數組中找到第 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<k;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<length && nums[i]<nums[left]{//左子樹大，交換
nums[i],nums[left]=nums[left],nums[i]
ll:=left*2 1
rr:=ll 1
if ll<length && nums[left]<nums[ll] || rr<length && nums[left]<nums[rr]{
//左子樹交換後，新的左子樹不符合,跳轉到左子樹
i=left
continue
}
}
right:=left 1
if right<length && nums[i]<nums[right]{//右子樹大，交換
nums[i],nums[right]=nums[right],nums[i]
ll:=right*2 1
rr:=ll 1
if ll<length && nums[right]<nums[ll] || rr<length && nums[right]<nums[rr]{
//新的右子樹不符合，跳轉到右子樹
i=right
continue
}
}
i--
}
}
執行時間：92ms 貌似效果不太好，複雜度更高了
再次優化：構建小頂堆，維持大小為K的數據，堆頂為結果。（代碼參考自大神的提交）
func findKthLargest(nums []int, k int) int {
m := new(MinHeap)
for i:=0;i<k;i {//前k個數直接push進堆
m.push(nums[i])
}
for i:=k;i<len(nums);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<this.index; {
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！
更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!
zpostcode 
Recruit 
weather 
mreligion 
Yellowpages 
sport 
constellation 
shopping 
name 
game 
directory 
literature 
Word 
tour 
furnish 
Lottery 
tftnews 
lyrics 
News 
digital 
car 
dir 
Edu 
Finance 
