关于公约数的循环列表问题

关于公约数的循环列表问题

问题:一个列表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. 如果只是简单的从第1个开始位移到第12个以后的话,最终只能有3个元素位移
  2. 如果暴力的使一个元素位移12次的话,那这个循环将会占用大量的时间,一个元素就要循环12次,如果k非常大的话,那这个程序的执行时间会非常的长。
  3. 如果结合前两种方法,外循环是18,内部让其直接移动到第12个位置,那当外循环到12时,12又会再次位移,但这并不是我们所想要的结果。
  4. 所以我的程序是结合了上面3点的不足,外循环是n和k的最大公约数,内循环是让当前元素向后移动到正确位置,再将被占用位置的原有元素向后移动,以此类推。我的程序是逆序完成的这个过程,也就是从后向前移动。
Comments are closed.