数组中的第K个最大元素golang版本

数组中的第K个最大元素

//解法一
type IntHeap []int
func (h IntHeap) Len()  int {
	return len(h)
}
func (h IntHeap) Less(i,j int) bool {
	return h[i] < h[j]
}
func (h IntHeap) Swap(i,j int)  {
	h[i],h[j] = h[j],h[i]
}
func (h IntHeap) Top() int {
	return h[0]
}
func (h *IntHeap) Push(x interface{})  {
	*h = append(*h, x.(int))
}
func (h *IntHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0:n-1]
	return x
}

func findKthLargest(nums []int,k int) int{
	h := &IntHeap{}
	heap.Init(h)
	for _,num := range nums{
		if h.Len() < k{
			heap.Push(h,num)
		}else if (*h)[0] < num{
			heap.Pop(h)
			heap.Push(h,num)
		}
	}
	return heap.Pop(h).(int)
}
//解法二
func findKthLarget(nums []int,k int) int{
	rand.Seed(time.Now().UnixNano())
	return quickSelect(nums,0,len(nums)-1,k)
}

func quickSelect(nums []int,l, r int, k int) int{
	m := randomPartition(nums,l,r)
	if r - m + 1 == k{
		return nums[m]
	}else if r-m+1 > k{
		return quickSelect(nums,m+1,r,k)
	}else{
		return quickSelect(nums,l,m-1,k-(r-m+1))
	}
}

func randomPartition(nums []int,l,r int) int{
	i := rand.Int() % (r - l + 1) + l
	nums[i],nums[r] = nums[r],nums[i]
	return partition(nums,l,r)
}

func partition(nums []int,l int,r int) int{
	key := nums[r]
	i := l
	j := l
	for j < r{
		if nums[j] < key{
			nums[i],nums[j] = nums[j],nums[i]
			i++
		}
		j++
	}
	nums[i],nums[r] = nums[r],nums[i]
	return i
}