go语言数组和切片的区别（数组中的第K个最大元素）

题目：

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

,