Force buckle topic link 1 force buckle topic link 2 cattle guest topic link
This problem is a classic problem, there are many solutions. The above questions are slightly different, please pay attention to the requirements. The following codes are for link 1 of force buckle, all submitted.
Method a
Sort it all the way from smallest to largest, and then take the first k numbers.
import "sort"
func smallestK(arr []int, k int) []int {
if k < 1 {
return nil
}
l := len(arr)
if l < k {
return nil
}
if l == k {
return arr
}
sort.Sort(sort.IntSlice(arr))
return arr[:k]
}
Copy the codeAssume that based on quicksort, the time complexity is O(nlogn)O(nlogn)O(nlogn) O(nlogn), and the space complexity is O(logn)O(logn)O(logn) O(logn).
Method 2
Based on the small top heap. Resize the array in place to the small top heap, and pop up the k number at the top of the heap.
func smallestK(arr []int, k int) []int {
if k == 0 {
return []int{}
}
l := len(arr)
if l <= k {
return arr
}
if l < 2 {
return arr
}
e := l- 1
for i := l/2- 1; i >= 0; i-- {
heapify(arr, i, e)
}
var j int
for i := l- 1; i > 0; i-- {
arr[i], arr[0] = arr[0], arr[i]
j++
if j == k {
break
}
heapify(arr, 0, i- 1)}return arr[l-k:]
}
/ / small cap pile
func heapify(a []int, s, e int) {
i := s
temp := a[i]
j := 2*i+1
for i < e && j <= e {
if j+1 <= e && a[j+1] < a[j] {
j++
}
if a[j] >= temp {
break
}
a[i] = a[j]
i = j
j = 2*i+1
}
a[i] = temp
}
Copy the codeTime complexity O(nlogn)O(nlogn)O(nlogn) O(nlogn) space complexity O(1)O(1)O(1).
Method three
Based on the big top heap. The big top heap requires additional storage space for k numbers. The array is iterated sequentially, pushing the elements into the heap until the number of valid data in the heap reaches K. Each element is then compared to the number at the top of the heap. If the value of the element is less than the number at the top of the heap, the number at the top of the heap is replaced and the heap is adjusted until all of the array elements are iterated. That k number in the heap is the result.
func smallestK(arr []int, k int) []int {
if k <= 0 {
return nil
}
l := len(arr)
if l < k {
return nil
}
if l == k {
return arr
}
// l > k
h := NewMaxHeap(k)
var i int
for i < l {
h.Push(arr[i])
i++
if h.Size() >= k {
break}}for i < l {
n := arr[i]
if n < h.Top() {
h.ReplaceTop(n)
}
i++
}
return h.Get()
}
/ / big heap
type MaxHeap struct {
data []int
size int
}
func NewMaxHeap(k int) *MaxHeap {
return &MaxHeap{
data: make([]int, k),
}
}
func (o *MaxHeap) Size(a) int {
return o.size
}
func (o *MaxHeap) IsEmpty(a) bool {
return o.size == 0
}
func (o *MaxHeap) Push(n int) {
o.data[o.size] = n
o.size++
o.siftUp()
}
func (o *MaxHeap) siftUp(a) {
if o.size < 2 {
return
}
child := o.size- 1
childVal := o.data[child]
for child > 0 {
p := (child- 1) /2 // parent
pV := o.data[p]
if pV >= childVal {
break
}
o.data[child] = pV
child = p
}
o.data[child] = childVal
}
func (o *MaxHeap) Top(a) int {
if o.IsEmpty() {
panic("MaxHeap is empty")}return o.data[0]}func (o *MaxHeap) ReplaceTop(n int) {
if o.IsEmpty() {
panic("MaxHeap is empty")
}
o.data[0] = n
o.siftDown()
}
func (o *MaxHeap) siftDown(a) {
if o.size < 2 {
return
}
var p int
pV := o.data[p]
for {
child := 2*p + 1
if child >= o.size {
break
}
if child+1 < o.size && o.data[child+1] > o.data[child] {
child++
}
if pV >= o.data[child] {
break
}
o.data[p] = o.data[child]
p = child
}
o.data[p] = pV
}
func (o *MaxHeap) Get(a) []int {
return o.data
}
Copy the codeTime complexity O(nlogk)O(nlogk)O(nlogk) O(nlogk) space complexity O(k)O(k)O(k).
Method four
Fast selection algorithm.
- The recursive implementation
func smallestK(arr []int, k int) []int {
if k <= 0 {
return nil
}
l := len(arr)
if k >= l {
return arr
}
quickSelect(arr, 0, l- 1, k)
return arr[:k]
}
func quickSelect(arr []int, low, high, k int) {
pivotIdx := doPivot(arr, low, high)
if pivotIdx == k- 1 {
return
}
if pivotIdx < k- 1 {
low = pivotIdx+1
} else if pivotIdx > k- 1 {
high = pivotIdx- 1
}
quickSelect(arr, low, high, k)
}
func doPivot(arr []int, low, high int) int {
medianOfThree(arr, low, high)
pivot := arr[low]
for low < high {
for low < high && arr[high] >= pivot {
high--
}
arr[low] = arr[high]
for low < high && arr[low] <= pivot {
low++
}
arr[high] = arr[low]
}
arr[low] = pivot
return low
}
func medianOfThree(arr []int, low, high int) {
mid := low+(high-low)>>1
if arr[mid] > arr[high] {
arr[mid], arr[high] = arr[high], arr[mid]
}
if arr[low] > arr[high] {
arr[low], arr[high] = arr[high], arr[low]
}
if arr[low] < arr[mid] {
arr[low], arr[mid] = arr[mid], arr[low]
}
}
Copy the codeQuick selection. Recursion. Time complexity: optimal O(n), worst O(n^2). Space complexity: optimal O(logn), worst O(n).
- Non-recursive implementation
func smallestK(arr []int, k int) []int {
if k == 0 {
return []int{}
}
l := len(arr)
if l < 2 {
return arr
}
if l <= k {
return arr
}
var (
low int
high = l- 1
)
for low < high {
pivotIndex := doPivot(arr, low, high)
if pivotIndex+1 == k {
break
} else if pivotIndex+1 < k {
low = pivotIndex+1 // Look in the next interval
} else {
high = pivotIndex- 1 // Look in the previous interval}}return arr[:k]
}
// From small to big
func doPivot(a []int, low, high int) int {
// Select the right number
// high - low + 1 >= 3
if high - low > 1 {
m := low + (high-low)/2
if a[m] > a[high] {
a[m], a[high] = a[high], a[m]
}
if a[low] > a[high] {
a[low], a[high] = a[high], a[low]
}
if a[m] > a[low] {
a[m], a[low] = a[low], a[m]
}
// a[m] <= a[low] <= a[high]
}
pivot := a[low]
for low < high {
for low < high && a[high] >= pivot {
high--
}
a[low] = a[high]
for low < high && a[low] <= pivot {
low++
}
a[high] = a[low]
}
a[low] = pivot
return low
}
Copy the codeQuick selection. The recursion. Time complexity: optimal O(n), worst O(n^2). Spatial complexity: O(1) because of in-place processing.
Solution to five
BFPRT algorithm.
func smallestK(arr []int, k int) []int {
if k < 1 {
return nil
}
l := len(arr)
if l == 0 {
return nil
}
if l < k {
return nil
}
if l == k {
return arr
}
// l > k
kthSmallest(arr, 0, l- 1, k)
return arr[:k]
}
func kthSmallest(nums[] int, low, high, k int) int {
for low < high {
pivotIndex := selectPivot(nums, low, high)
pivotIndex = partition(nums, low, high, pivotIndex, k)
if k- 1 < pivotIndex {
high = pivotIndex- 1
} else if k- 1 == pivotIndex {
return pivotIndex
} else {
low = pivotIndex+1}}return low
}
func selectPivot(nums []int, low, high int) int {
if high-low+1< =5 {
return partition5(nums, low, high)
}
// median of medians
t := low
for i := low; i <= high; i += 5 {
j := i+4
if j > high {
j = high
}
m := partition5(nums, i, j)
t = low + (i-low)/5
nums[m], nums[t] = nums[t], nums[m]
}
mid := low + (t-low)>>1
if (t-low+1) &1= =0 {
mid++ // Lower median
}
return kthSmallest(nums, low, t, mid)
}
func partition(nums []int, low, high, pivotIndex, kth int) int {
// a three-way partition
var (
i = low
j = low
k = high
pivot = nums[pivotIndex]
)
for j <= k {
n := nums[j]
if n < pivot {
nums[i], nums[j] = n, nums[i]
i++
j++
} else if n > pivot {
nums[j], nums[k] = nums[k], n
k--
} else {
j++
}
}
if kth- 1 < i {
return i
} else if kth- 1 < j {
return kth- 1
} else {
return k
}
}
func partition5(nums []int, low, high int) int {
// Insert sort directly from small to large
for i := low+1; i <= high; i++ {
n := nums[i]
j := i- 1
for j >= 0 && nums[j] > n {
nums[j+1] = nums[j]
j--
}
nums[j+1] = n
}
return low + (high-low)>>1
}
Copy the codeTime complexity O(n)O(n)O(n), but n usually has a large constant coefficient C.