golang struct数组排序_Go实现算法：数组中的第K个最大元素（LeetCode）

题目：

在未排序的数组中找到第 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！