关于公约数的循环列表问题
问题:一个列表a,a中有n个元素,向右移动k位,如果是列表中的最后一个元素,向右移动1位,那它会移动到列表的第一个位置,n和k都是任意正整数。最后根据列表q中的索引号,返回右移后的列表a中相应元素。
如:列表a=[1,2,3,4,5,6],k=2 ,q=[3,2,1,0] 返回的列表应该是[2,1,6,5]
下面是我的代码
import math
def circularArrayRotation(a, k, queries):
temp=0
len_a=len(a)
k=k%len_a
gcd_num=math.gcd(k,len_a)
for start in range(gcd_num):
i=start
temp=a[i]
while True:
a[i]=a[i-k]
#这里是为了防止i-=k会溢出列表,所以用了取模操作
i=(i-k)%len_a
if i==start:
break
a[(i+k)%len_a]=temp
return [a[x] for x in queries]
ps:红色部分很重要,因为当k和n之间有除了1之外的最大公约数的时候,有一些数始终不会被循环到。如果使用顺序循环的话,那当k不是1的时候就会有多个被覆盖的列表元素,为了让被覆盖的元素始终只有1个,就要备份第k个元素,然后把当前元素赋值给第k个元素,但是这个逻辑不能正序进行(因为a[i+nk]=a[i]会把列表中所有的值都变成同样的),所以要从后向前逆向传递才可以(PS:也就是a[i]=a[i-nk]),最后再把备份的第一个元素赋值给最后一个元素。
比如:n=18,k=12,
- 如果只是简单的从第1个开始位移到第12个以后的话,最终只能有3个元素位移
- 如果暴力的使一个元素位移12次的话,那这个循环将会占用大量的时间,一个元素就要循环12次,如果k非常大的话,那这个程序的执行时间会非常的长。
- 如果结合前两种方法,外循环是18,内部让其直接移动到第12个位置,那当外循环到12时,12又会再次位移,但这并不是我们所想要的结果。
- 所以我的程序是结合了上面3点的不足,外循环是n和k的最大公约数,内循环是让当前元素向后移动到正确位置,再将被占用位置的原有元素向后移动,以此类推。我的程序是逆序完成的这个过程,也就是从后向前移动。