题目：
在未排序的数组中找到第
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 数组 右子树
