这是一个创建于 265 天前的主题，其中的信息可能已经有所发展或是发生改变。
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)
}
请教一下输出的为什么不是[3 20 30] 呀， 感觉使用好像和 python 的不太一样
5 条回复 • 2024-03-21 23:16:20 +08:00
 |
1
kfish 265 天前
很明显不是切片的问题, 算法没写对呗
|
 |
2
nagisaushio 265 天前 via Android
tmp := append(q.arr[:index], num) 这句会覆写后面已有的数据
|
 |
3
18870715400 OP @nagisaushio 大佬， 由于我这边是从 python 转过来的，python 类似的就是这样的写法，不知道这样具体有啥问题呢。
|
 |
4
NilXuan 265 天前
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)就是正常的操作了。 |
Select Language