package main
import "fmt"
type pq struct {
arr []int
}
func (q *pq) put(num int) {
// 从小到大的顺序插入进去
index := b_s(q.arr, num)
if index >= len(q.arr) {
// 直接插到最后一个数位
q.arr = append(q.arr, num)
} else {
tmp := append(q.arr[:index], num)
tmp = append(tmp, q.arr[index:]...)
q.arr = tmp
}
}
func (q *pq) get() int {
if len(q.arr) > 0 {
num := q.arr[0]
q.arr = q.arr[1:]
return num
}
panic("arr is empty!!!")
}
func (q *pq) getSize() int {
return len(q.arr)
}
func b_s(arr []int, target_num int) int {
if len(arr) == 0 {
return 0
} else {
left, right := 0, len(arr)-1
for {
if right-left <= 1 {
if target_num <= arr[left] {
return left
} else if target_num <= arr[right] {
return right
} else {
return right + 1
}
} else {
mid := (left + right) / 2
if arr[mid] == target_num {
return mid
} else if arr[mid] < target_num {
left = mid
} else {
right = mid
}
}
}
}
}
func main() {
s := &pq{arr: make([]int, 0)}
s.put(20)
s.put(3)
s.put(30)
fmt.Println(s.arr)
}
1
kfish 231 天前
很明显不是切片的问题, 算法没写对呗
|
2
nagisaushio 231 天前 via Android
tmp := append(q.arr[:index], num) 这句会覆写后面已有的数据
|
3
18870715400 OP @nagisaushio 大佬, 由于我这边是从 python 转过来的,python 类似的就是这样的写法,不知道这样具体有啥问题呢。
|
4
NilXuan 231 天前
tmp := append(q.arr[:index], num);可以看做两条语句:
a := q.arr[:index]; tmp := append(a,num); 问题的关键在于关键的问题:a 虽然是一个新的切片变量,但是 a 的底层数据结构——数组是和 q.arr 共享的;因此 tmp := append(a,num); 相当于把 num 放到了底层数组 index 的位置,那么从 q.arr 的角度来看,就是数据被覆盖了; 可以尝试新创建一个数组,然后 copy 一下; |
5
18870715400 OP @NilXuan 感谢大佬,看了一下解释,
第一次 put(20)的时候是正常没有问题, 第二次 put(3)的时候是发生了以下的过程 首先计算出来 index=0 , 所以 tmp := append(q.arr[:index], num)就变成了以下两个步骤 a := q.arr[:0], 所以切片截取之后 a 和 q.arr 的 header 地址相同,len 不同,q.arr 是 1 ,a=0 ,cap 一样, tmp := append(a, num), 此时没有发生扩容,所以 a 和 q.arr 还是使用的同一片地址, 所以第一个元素就改成了 num 就是 3 了 tmp = append(tmp, q.arr[index:]...) 所以此时 q.arr[index:] 就是 等于 [3]了 此时 append 进行了扩容,tmp 会迁移到一个新的地址当中,所以此时 tmp 就是[3, 3]了, 而之前的 q.arr 还是[3] 之后 put(30)就是正常的操作了。 |