JZ29 最小的K个数

最小的K个数

给定一个数组，找出其中最小的K个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。如果K>数组的长度，那么返回一个空的数组

方法1：堆
思路和算法

我们用一个大根堆实时维护数组的前 k 小值。首先将前 k 个数插入大根堆中，随后从第 k+1个数开始遍历，如果当前遍历到的数比大根堆的堆顶的数要小，就把堆顶的数弹出，再插入当前遍历到的数。最后将大根堆里的数存入数组返回即可。在下面的代码中，由于 C++ 语言中的堆（即优先队列）为大根堆，我们可以这么做。而 Python 语言中的堆为小根堆，因此我们要对数组中所有的数取其相反数，才能使用小根堆维护前 k 小值。

方法2、用快排最最最高效解决 TopK 问题：O(N)O(N)
注意找前 K 大/前 K 小问题不需要对整个数组进行 O(NlogN)O(NlogN) 的排序！
例如本题，直接通过快排切分排好第 K 小的数（下标为 K-1），那么它左边的数就是比它小的另外 K-1 个数啦～

func getLeastNumbers(arr []int, k int) []int {
    if len(arr)==0 || k==0 {
        return nil
    }

    //方法一 基于快排的快速选择
    // return quicksearch(arr, 0, len(arr)-1, k)

    //方法二 快排 然后取前k个
    // quicksort(arr, 0, len(arr)-1)
    // return arr[:k]


    //方法三  建堆，大根堆
    d:=&heapInt{}
    for _,v:=range arr {
        if d.Len()<k {
            heap.Push(d,v)
        }else {
            if d.Peek()>v {
                heap.Pop(d)
                heap.Push(d,v)
            }
        }
    }
    return *d


}

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

func quicksearch(nums []int,i,j,k int) []int{
    
    t:=partition(nums,i,j)

    if t==k-1 {
        return nums[:k]
    }

    if t<k-1 {
        return quicksearch(nums,t+1,j,k)
    }


    return quicksearch(nums,i,t-1,k)
    
}

func quicksort(nums []int,i,j int) {
    if i>=j {
        return
    }

    m:=partition(nums, i,j)
    quicksort(nums,i,m-1)
    quicksort(nums,m+1,j)
}

type heapInt []int

//Less  小于就是小跟堆，大于号就是大根堆
func (h *heapInt)Less(i,j int)bool {return (*h)[i]>(*h)[j]}
func (h *heapInt)Swap(i,j int) {(*h)[i],(*h)[j]=(*h)[j],(*h)[i]}
func (h *heapInt)Len() int {return len(*h)}
func (h *heapInt)Push(x interface{}) {
    *h=append(*h,x.(int))
}
func (h *heapInt)Pop() interface{} {
    t:=(*h)[len(*h)-1]
    *h=(*h)[:len(*h)-1]
    return t
}
func (h *heapInt)Peek() int {
    return (*h)[0]
}
`