遇上了才知道自己很容易忽略切片中的地址为引用

这是一个我在刷算法题的时候遇到的问题,困了我一个下午没想出来是为什么。
题目:子集

这是我出现问题的那版代码
可以明显的发现红框的两个地方其实是一个 leftArr ,但是在经过一次函数调用后就被修改了

0

为什么会出现这种情况呢?

让我们来分析一下代码,其实 search 函数是一个 前序遍历 ,内部有两个递归函数
所以 search 函数一开始会先执行第 19 行一直递归到 index == len(nums) 也就是 index == 5 时返回最后的 temp = [0, 3, 5, 7, 9]
既然代码的报错处 index = 3,我们就可以先从此时开始分析(画了个图方便看)

0

  • index = 3 时,temp = [0, 3, 5](先是一直走 leftArr 所以 temp 包含了前面的所有值)
  • 首先继续走 leftArr ,此时 temp = [0, 3, 5, 7],因为最上面的结果图显示是第四个值被改变了,此时第四个值已经存在,所以 index = 4 之后可以不被考虑
  • 然后返回 index = 3,走 rightArr,此时 temp = [0, 3, 5],第四个索引处没有值
  • 最后再走 leftArr 时,num[4] = 9 赋值给了此时 temp 的第四个索引处导致 temp = [0, 3, 5, 9]

最后再看下各个时期的 temp

0可以发现,虽然 temp 长度只有 3,但是 cap 却已经有 4 这就导致地址 temp[3] 的地址早已被分配,之后没对 temp[3] 做一次修改都会影响到之前的结果。 sob: 真的是头很痛啊,所以 slice 一定要谨慎呀。

本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 6

@LiuKaHo
file
append时如果超出原有的 cap 时,len只会+1,但是cap是成倍增长,所以导致这里temp[3]被提前分配
真的是好气啊

5年前 评论

@LiuKaHo 就是单纯按 cap = 2*len 来扩容的

5年前 评论

@LiuKaHo 可以,看到那个 newcap += newcap / 4

5年前 评论

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!