???????? 本文主要陳述實現數組中元素旋轉移位（以左移為例）的三種方法！其中第一種方法和第三種方法的時間復雜度為O(n),空間復雜度為1。第二種方法方法的時間復雜度為O(n),空間復雜度為i。【其中i為移動的位數，n為總位數】具體程序如下:
@1:
//【編程珠璣第二版P13上 移位的雜技表演法時間復雜度為O(n),空間復雜度為1】這種方法，筆者感覺非常好！筆者將針對這種方法專門寫一篇BLOG！
#include <iostream>
using namespace std;int gcd(int a, int b){if(a * b == 0){return 0;}while(a != b){if(a > b)a -= b;elseb -= a;}return a;
}void rotate(int * x, int n, int rotdist){ //時間復雜度為O(n)，空間復雜度為1【t = x[i]】，效率高int i, l = gcd(rotdist, n), k, t, j;for(i = 0; i < l; ++ i){ t = x[i];j = i;while(1){k = j + rotdist;if(k >= n)k -= n;if(k == i)break;x[j] = x[k];j = k;} x[j] = t; //t不能換成是x[k]或者x[i]，因為x[i]已經被賦值為新的內容了！這也正是引入變量t的原因 }
}int main(){int array[] = {1, 3, 6, 2, 29, 3, 4, 5, 17};int length = sizeof(array)/sizeof(array[0]);int j;for(j = 0; j < length; ++ j){printf("%d\t", array[j]);}printf("\n");rotate(array, length, 3); //間隔為3for(j = 0; j < length; ++ j){printf("%d\t", array[j]);}printf("\n");return 0;
}
@2:?
//【移位的普通方法，時間復雜度為O(n),空間復雜度為i】
#include <stdio.h>
#include <stdlib.h>void rotate(int * x, int n, int i){ //此算法每個元素只移動一次，所以時間復雜度為O(n),空間復雜度為i【數組arrtem】int j, t, k, temp, temp1, *arrtem;arrtem = (int *)malloc(i * sizeof(int));for(j = 0; j < i; ++ j){t= x[j];k = 0;temp1 = j; while(1){temp = temp1 ; //temp1可換為k * i % n。此處寫為temp1可能讓人不太容易懂，但有效的避免了重復計算。++k;temp1 = (k * i + j)% n ;if(temp1 < temp){ break;}else{x[temp] = x[temp1];}}arrtem[j] = t;}for(j = 0; j < i; ++ j){x[n - i + j] = arrtem[j];}free(arrtem);
}void main(){int array[] = {1, 3, 6, 2, 29, 13, 5};int length = sizeof(array)/sizeof(array[0]);int j;for(j = 0; j < length; ++ j){printf("%d\t", array[j]);}printf("\n");rotate(array, length, 4); //間隔為4for(j = 0; j < length; ++ j){printf("%d\t", array[j]);}printf("\n");
}
?
@3:
//【編程珠璣第二版P13下手搖法實現移位:三次調用reverse函數】此算法時間復雜度為O(n),空間復雜度為1
#include <iostream>
using namespace std;void reverse(int * array, int beg, int end){int front = beg;int behind = end;int temp;while(front < behind){temp = array[front];array[front] = array[behind];array[behind] = temp;++ front;-- behind;}
}
int main(){int arr[] = {1, 29, 38, 2, 8, 12};int i = 2;int n = sizeof(arr)/sizeof(arr[0]);int j;for(j = 0; j < n; ++ j){cout<<arr[j]<<'\t';}cout<<endl;reverse(arr, 0, i - 1);reverse(arr, i, n - 1);reverse(arr, 0, n - 1);for(j = 0; j < n; ++ j){cout<<arr[j]<<'\t';}cout<<endl;return 0;
}
?
?
如果您對本博文有什么意見，歡迎您與我聯系！【我的郵箱】:lxw0109@gmail.com
總結
以上是生活随笔為你收集整理的数组中元素旋转移位的三种实现方法 --By LXW的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
