已知一个几乎有序的数组。几乎有序是指,如果把数组排好序的话,每个元素移动的距离一定不超过k,并且k相对于数组的长度来讲是比较小的。
请选择一个合适的排序策略,对这个数组进行排序是最好的。
[x,x,x,x,xx,x] k = 5
排序的话,每一个数字去的位置不超过5
生成一个小根堆
i - i 0
i - i + 1 1
i - i - 1 1
前k + 1 个数进小根堆
堆中0 - 5 的位置会来到0位置
从小根堆中d出最小值放到0位置,6位置的数不可能来到0位置,因为距离是6
将6加入小根堆。。。
从小根堆中d出最小值放到1位置
将7加入小根堆。。。
。。。。
package heap
import (
"container/heap"
"fmt"
"testing"
)
type IntHeap []int // 定义IntHeap类型
/*
实现container/heap 的接口
type Interface interface {
sort.Interface
Push(x interface{}) // add x as element Len()
Pop() interface{} // remove and return element Len() - 1.
}
*/
func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool {
return h[i] < h[j] // 如果h[i]h[j]生成的就是大根堆
}
func (h IntHeap) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
func (h *IntHeap) Pop() interface{} { // 绑定pop方法,从最后拿出一个元素并返回
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
func (h *IntHeap) Push(x interface{}) { // 绑定push方法,插入新元素
*h = append(*h, x.(int))
}
func TestGoHeapDemo(t *testing.T) {
iheap := &IntHeap{}
heap.Init(iheap) // 绑定类型
heap.Push(iheap,3)
heap.Push(iheap,1)
heap.Push(iheap,30)
heap.Push(iheap,3222)
heap.Push(iheap,34)
fmt.Println(heap.Pop(iheap))
fmt.Println(heap.Pop(iheap))
fmt.Println(heap.Pop(iheap))
fmt.Println(heap.Pop(iheap))
}
func SortArrayDistanceLessK(arr []int, k int) {
iHeap := &IntHeap{}
heap.Init(iHeap) // 绑定类型
index := 0
for ; index <= min(len(arr) - 1 , k ); index++ {
heap.Push(iHeap,arr[index])
}
i := 0
for ; index < len(arr); i, index = i + 1, index + 1 {
heap.Push(iHeap,arr[index]) //先加一个 再d出 或先d出再加都可以
arr[i] = heap.Pop(iHeap).(int)
}
for len(*iHeap) != 0 { //后面的几个值依次d出就行了,沿途的可以一边加一边d
arr[i] = heap.Pop(iHeap).(int)
i++
}
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
func TestSortArrayDistanceLessK(t *testing.T) {
arr := []int{1,3,4,2,3,7,6,8,10,6,9}
SortArrayDistanceLessK(arr,3) //O(n * logk)
fmt.Println(arr)
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)