funcpartition(arr []int, start int, end int)int { rand.Seed(time.Now().UnixNano())
index := rand.Intn(end-start+1) + start val := arr[index] arr[index], arr[start] = arr[start], arr[index]
for start < end { for start < end && val <= arr[end] { end-- } arr[start] = arr[end] for start < end && val >= arr[start] { start++ } arr[end] = arr[start] } arr[start] = val return start }
funcgetLeastNumbers(arr []int, k int) []int { //特殊情况 iflen(arr) == 0 || k <= 0 { returnnil } elseif k >= len(arr) { return arr }
index := partition(arr, 0, len(arr)-1) for index != k-1 { if index > k-1 { //说明在左边 index = partition(arr, 0, index-1)
} elseif index < k-1 { index = partition(arr, index+1, len(arr)-1) } } //到这里说明partition划分为index就是第k个元素,直接返回即可 return arr[:k] }