數(shù)組循環(huán)向左移動k位的算法, 我在課本上只看到了方法一,暫且稱為顛倒交換法, 方法二是我自己想出來的,暫且稱為循環(huán)賦值法.

方法一:顛倒交換法

算法描述:循環(huán)左移k位, 先把前面 0 到 k-1位置的數(shù)字首尾交換, 然后再把 k 到 len-1位置首尾交換, 最后再把 0 到 len-1下標位置首位交換即可實現(xiàn), 這里的原理你可以畫個例子就懂了

代碼:

int a[100]; //數(shù)組是全局變量//輸出0到len位置的元素 void show(int len){for(int i=0;i<len;i++){printf("%d ",a[i]);} }//首尾交換的函數(shù) 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長度的數(shù)組printf("\n\n"); }

方法二:循環(huán)賦值法

這個方法是我自己想出來的, 也很感謝@木落兮幫我指正的錯誤, 如果還有錯誤的地方, 歡迎各位評論指正錯誤
算法描述:

• 情況1:針對len%k!=0
  舉個例子，len=5, k=3時 畫個圖把代碼走一遍，看下面的圖
  
• 情況2 針對len%k==0
  讓count用來計數(shù)循環(huán)的趟數(shù), 比如 len=10, k=2 時,count范圍從0~1 循環(huán)兩次
  內層循環(huán) 使用 i 和 j 來循環(huán)賦值,當回到count下標位置時,這一趟賦值完成,繼續(xù)下一趟

綜上所述,這個算法循環(huán)了k趟, 每趟循環(huán) len/k 次, 時間復雜度O(n), 空間復雜度O(1)

代碼:

//方法二: 循環(huán)移動法 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的整數(shù)倍int temp = a[0];while(true){j = (i+k)%len; //j取i后面的k+i位置,如果超出范圍,則取余if(j==0) //如果循環(huán)一大圈,則說明已經(jīng)賦值完成了就break,但是這個方法針對len%k==0的情況失效,所以while循環(huán)套在if判斷里面break;a[i] = a[j];i = j;}a[i] = temp;}else{ //情況二:如果len是k的整數(shù)倍,由于上述情況不能適用于整數(shù)倍的情況for(int count=0;count<k;count++){ //循環(huán)k趟i = count;temp = a[i]; //記錄開始的位置while(true){j = (i+k)%len;if(j==count) break; //回到這個位置時,則跳出循環(huán)a[i] = a[j];i = j;}a[i] = temp;} //end for} //end ifshow(len); //輸出len長度的數(shù)組}

附錄:方法二的修改版, 壓縮為一個循環(huán)

算法描述:
當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; //循環(huán)的趟數(shù),循環(huán)k次int pos = 0; //標記每趟循環(huán)開始的位置while(true){j = (i+k)%len;if(j<k && ++count==k) //標記循環(huán)的趟數(shù),超過k次,則跳出循環(huán)break;if(j==pos){ // 如果j與pos重合,就說明是len%k==0的情況,則讓a=j+1,再來一趟循環(huán)a[i] = temp;i=j+1;temp = a[i];pos = i; //標記這一趟開始的位置continue; //跳過下面兩行代碼}a[i] = a[j];i = j;} //end whilea[i] = temp; //這一句代碼針對len%k!=0的情況,讓最后一個位置賦值show(len); //輸出len長度的數(shù)組 }

如果你覺得算法有待改進的地方, 可以在下面評論。

總結

以上是生活随笔為你收集整理的数组循环向左移动k位的算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。