我有运行代码从堆栈中删除中间元素,这不是问题。这是我的代码;
def insert(stack,temp,curr,n):
#print(curr,stack)
if curr!=n//2:
print(curr)
stack.append(temp)
#return
return
def delete_middle(stack,n,curr):
while len(stack)>0:
temp=stack.pop()
delete_middle(stack,n,curr+1)
insert(stack,temp,curr,n)
#print(stack)
return stack
delete_middle([2,4,1,18,34],5,0)
我的代码工作正常。但我试图了解递归堆栈是如何工作的。例如,我们正在对delete_middle()
进行大约5
次的递归调用(与列表长度相同,stack
)。每次指针变量curr
更新为指向当前元素时。如您所见,curr
的最后一个值将是 5,但由于堆栈的长度为 0,因此不再有递归调用。然后调用insert()
函数。
有趣的是,如果我查看insert()
内部的curr
值,我们得到以下输出;
4
3
2
1
0
为什么我们在这里没有看到curr
的第一个值为 5?我将非常感谢这里的一些反馈。我能对它的时间复杂度有一些想法吗?似乎O(N)
N
堆栈的大小。但我对此有点生疏。将在这里欣赏一些见解。 谢谢
编辑:
只有在递归函数使用空堆栈后,才会执行插入函数。
START DELETE 0 [only one while loop executed]
START DELETE 1 [only one while loop executed]
START DELETE 2 [only one while loop executed]
START DELETE 3 [only one while loop executed]
START DELETE 4 [only one while loop executed]
START DELETE 5 [NO while loop executed because list is empty]
-------------------------
START INSERT iteration 4
END INSERT iteration 4
END DELETE 4
-------------------------
START INSERT iteration 3
END INSERT iteration 3
END DELETE 3
-------------------------
START INSERT iteration 2
END INSERT iteration 2
END DELETE 2
-------------------------
START INSERT iteration 1
END INSERT iteration 1
END DELETE 1
-------------------------
START INSERT iteration 0
END INSERT iteration 0
END DELETE 0
因此,我们首先运行插入函数 (4),因为当执行最后一个 delete_middle(5) 时,列表 stack 为空,并且它不会运行插入函数,如前所述:
while len(stack)>0:
...........
insert(stack,temp,curr,n)
以上与n=5
delete_middle
将不会执行,因为len(stack)==0
.
中间如何工作:
#first executed delete_middle([2,4,1,18,34],5,0)
def delete_middle(stack,n,curr): iteration 1
while len(stack)>0: initial stack [2,4,1,18,34]
temp=stack.pop() stack after removal [2,4,1,18]
.....
delete_middle(stack,n,curr+1) -> becomes: delete_middle([2,4,1,18],5,1) iteration 2
while len(stack)>0: initial stack [2,4,1,18]
temp=stack.pop() stack after removal [2,4,1]
.....
delete_middle(stack,n,curr+1) > becomes: delete_middle([2,4,1],5,2) and so on until stack = [] (empty)
.....
(!) During these iterations insert(stack,temp,curr,n) is not executed because:
插入如何运行:
delete_middle([2,4,1,18,34],5,0)
# Iteration 1
#delete_middle(stack, n, curr+1)
delete_middle([2,4,1,18], 5, 1 )
insert not executed!
# Iteration 2
delete_middle([2,4,1],5,2)
insert not executed!
# Iteration 3
delete_middle([2,4],5,3)
insert not executed!
# Iteration 4
delete_middle([2],5,4)
insert not executed!
# Iteration 5
delete_middle([],5,5) # returns nothing because it does not enter the while loop
insert not executed!
Only from now -> each insert will be executed from inside delete_middle!
insert 4
insert 3
insert 2
insert 1
关于时间复杂度:
Time complexity = time taken to build the final list;
= (1 pop + 1 insert) * n
= O(n)
在最坏-最坏情况下,您可以说复杂性为 O(n),因为将列表大小减少 1 个元素涉及将 1 个元素附加到列表中,这是因为每个级别只有一个递归。(而..返回缩进)
虽然 pop 是 O(1) 并且列表每次减少 (O(log n)),但当调用每个middle_delete
时,算法的运行时间会随着输入数据的大小而增加,通过总共执行 (n-1) 追加;附加整个剩余列表。
一些起点。
结束编辑
关于您的代码,是的,它可以工作,如果可以的话,有一些限制:
- 目标列表的长度必须为奇数
- 采取一些额外的不必要的*标准(
curr,n
)[不必要的见 最后一部分] - 函数未"完全正确"执行
解释:
自己尝试
回答结束(耐心等待我:))
- 例如:
在您的代码中:
while len(stack)>0:
.....
return stack
基本上,您似乎返回了 while 循环的第一个值。 例:
c = 0
def func(d):
while d < 5:
d+=1
return d
print(func(c))
递归效果是由 while 循环中巧妙地使用None
生成的 func(insert) 触发的。这就像拉手而不是踏板。:)
关于您的问题:
如下图所示,(执行中间函数 + 插入函数)为每个元素。
delete middle iterion 0
--------------------------
temp 34 0
delete middle iterion 1
--------------------------
temp 18 1
delete middle iterion 2
--------------------------
temp 1 2
delete middle iterion 3
--------------------------
temp 4 3
delete middle iterion 4
--------------------------
temp 2 4
delete middle iterion 5
--------------------------
======================
insert iteration 4
curr:4, stack:[], temp:2,n:5
======================
insert iteration 3
curr:3, stack:[2], temp:4,n:5
======================
insert iteration 2
curr:2, stack:[2, 4], temp:1,n:5
======================
insert iteration 1
curr:1, stack:[2, 4], temp:18,n:5
======================
insert iteration 0
curr:0, stack:[2, 4, 18], temp:34,n:5
[2, 4, 18, 34]
为什么我们在这里没有看到 curr 的第一个值为 5?
如果从 0 开始 (curr
),您将看到从 4->0 开始的迭代,而当初始 curr 为 1 时,迭代将为 5->1;因此将触发 5 (N) 个删除函数调用。
- 我用一个简单的逻辑重构了你的代码:
如果你有一个目标列表[1,2,..,n-1,n],如果你想使用递归函件删除中间部分,也许这种方法可能会吸引你:
让我们从 0 计数器count = 0
开始 对于列表中的每个元素,计数器将递增 1count+=1
现在,为了从每边(左,右)消除一个元素以到达中间,我们可以说:如果count为0或count甚至从列表中删除最后一项,如果不删除第一项,则列表每次迭代都会丢失一个项目。
if count == 0 and count % 2 == 0:
target_list.pop(-1)
else:
target_list.pop(0)
那么,如果列表包含偶数个项目怎么办?然后我们也将包括这个场景:if len(target) == 2
.
我还建议使用一个小技巧,即函数参数的默认值仅在定义函数时计算一次。
我这是什么意思?检查常见错误 #1 的示例。
要将上面的所有内容都包含到最终函数 (O(N)) 中:
def eliminate_middle(target, count=0, beg_l=[],end_l=[]):
print(count) # O(N)
if len(target) == 1: # if target has only one element
return beg_l+sorted(end_l)
else:
if count == 0 or count % 2 == 0:
if len(target) == 2: # case len(target) is Even
return beg_l+sorted(end_l) #eliminates the two middle elements
end_l.append(target.pop(-1)) #target loses last element
return eliminate_middle(target,count+1)
else:
beg_l.append(target.pop(0)) # target loses first element
return eliminate_middle(target, count+1)
print(eliminate_middle([2,4,1,18,34]))