数组循环向左移动k位的算法（转载）

原文链接：https://blog.csdn.net/wang342626/article/details/81713210

方法一:颠倒交换法

算法描述:循环左移k位, 先把前面 0 到 k-1位置的数字首尾交换, 然后再把 k 到 len-1位置首尾交换, 最后再把 0 到 len-1下标位置首位交换即可实现, 这里的原理你可以画个例子就懂了

代码:

int a[100]; //数组是全局变量
//输出0到len位置的元素
void show(int len){
for(int i=0;i<len;i++){
printf("%d ",a[i]);
}
}
//首尾交换的函数
void reverse(int left,int right){
int i=left,j=right;
while(i<j){
int t = a[i];
a[i] = a[j];
a[j] = t;
i++;
j--;
}
}
//方法一:颠倒交换法
void fun1(int len,int k){
int i=0;
for(i=0;i<len;i++)
a[i] = i;
reverse(0,k-1);
reverse(k,len-1);
reverse(0,len-1);
show(len); //输出len长度的数组
printf("nn");
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

方法二:循环赋值法

这个方法是我自己想出来的, 也很感谢@木落兮帮我指正的错误, 如果还有错误的地方, 欢迎各位评论指正错误
算法描述:

• 情况1:针对len%k!=0
  举个例子，len=5, k=3时 画个图把代码走一遍，看下面的图
  
• 情况2 针对len%k==0
  让count用来计数循环的趟数, 比如 len=10, k=2 时,count范围从0~1 循环两次
  内层循环 使用 i 和 j 来循环赋值,当回到count下标位置时,这一趟赋值完成,继续下一趟

综上所述,这个算法循环了k趟, 每趟循环 len/k 次, 时间复杂度O(n), 空间复杂度O(1)

代码:

//方法二: 循环移动法
void fun2(int len,int k){
int i;
for(i=0;i<len;i++)
a[i] = i;
int j,temp = a[0];
i=0;
if(len%k!=0){
//情况一:如果len不是k的整数倍
int temp = a[0];
while(true){
j = (i+k)%len; //j取i后面的k+i位置,如果超出范围,则取余
if(j==0) //如果循环一大圈,则说明已经赋值完成了就break,但是这个方法针对len%k==0的情况失效,所以while循环套在if判断里面
break;
a[i] = a[j];
i = j;
}
a[i] = temp;
}
else{ //情况二:如果len是k的整数倍,由于上述情况不能适用于整数倍的情况
for(int count=0;count<k;count++){ //循环k趟
i = count;
temp = a[i]; //记录开始的位置
while(true){
j = (i+k)%len;
if(j==count) break; //回到这个位置时,则跳出循环
a[i] = a[j];
i = j;
}
a[i] = temp;
} //end for
} //end if
show(len); //输出len长度的数组
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

附录:方法二的修改版, 压缩为一个循环

算法描述:
当len=8, k=2时, 如图

void fun3(int len,int k){
int i;
for(i=0;i<len;i++)
a[i] = i;
int j , temp = a[0];
i=0;
int count = 0; //循环的趟数,循环k次
int pos = 0; //标记每趟循环开始的位置
while(true){
j = (i+k)%len;
if(j<k && ++count==k) //标记循环的趟数,超过k次,则跳出循环
break;
if(j==pos){
// 如果j与pos重合,就说明是len%k==0的情况,则让a=j+1,再来一趟循环
a[i] = temp;
i=j+1;
temp = a[i];
pos = i; //标记这一趟开始的位置
continue; //跳过下面两行代码
}
a[i] = a[j];
i = j;
} //end while
a[i] = temp; //这一句代码针对len%k!=0的情况,让最后一个位置赋值
show(len); //输出len长度的数组
}

最后

以上就是生动纸飞机为你收集整理的数组循环向左移动k位的算法（转载）的全部内容，希望文章能够帮你解决数组循环向左移动k位的算法（转载）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。