七叶笔记 » golang编程 » Go实现算法:数组中的第K个最大元素(LeetCode)

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<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!

相关文章