題目：給一個數(shù)組，和長度，還有一個k值，將數(shù)組后移k個位置。注意：超過最后的位置的數(shù)組，會循環(huán)到第一個位置。
例如：arr[7] = {1,2,3,4,5,6,7}; len = 7; k = 3;
旋轉過后數(shù)組為：arr[7] = {5,6,7,1,2,3,4};
首先k = k%len;k和k = k%len效果一樣。比如上面例子，移7位和移0位一樣，優(yōu)化一下，k = %len。

本篇博客記錄以下幾種方法：
1.將最后一個元素拿出來保存到tmp中，其他元素都后移k個，將tmp賦值給第一個元素。重復操作k次即相當于每個元素都后移k個位置。
2.直接在原數(shù)組上交換，從arr[0]開始，找arr[0]的移動后的位置，將該位置的值和下標保存下來，將arr[0]放進去，然后找該位置本來的值的移動后的位置。交換len次即可。
3.整個數(shù)組逆置，再將前半部分和后半部分逆置。
4.找到下標移動后對應的下標，配合空間使用。

一、一次將元素移動一個單元格，操作k次

//將最后一個元素存放到tmp中，前面的元素向后移一個位置，重復k次操作。最后一個元素后移一位即放到第一個元素位置上 void move_one(int* arr, int len)//每個元素后移一位 {int tmp = arr[len - 1];//保存最后一個元素for (int i = len - 2; i >= 0; i--)//每個元素都向后移一個單元格{arr[i + 1] = arr[i];}arr[0] = tmp;//將原本的最后一個元素放到第一個位置上 }void Reversal_arr_1(int* arr, int len, int k) {assert(arr != NULL);k = k % len;for (int i = 1; i <= k; i++)//一次移一位，操作k次即移動k位{move_one(arr, len);} }

二、直接在原數(shù)組上交換，將被交換掉的元素再和其他元素交換

思路：如下圖

代碼：

//直接一個一個元素的找對應的位置，被替換掉的元素用tmp保存，找被替換掉的元素的位置 void Reversal_arr_2(int* arr, int len, int k)//k = 2 {assert(arr != NULL);k = k % len;int tmp = 0; //保存要被覆蓋的值int index = 0; //保存要被覆蓋的值的下標int cur = arr[0];//保存下一個要移動的值for (int i = 1; i <= len; i++)//len個元素，總共找len次位置就可以了{tmp = arr[(index + k) % len];//先保存即將被替換掉的值arr[(index + k) % len] = cur; //找到cur元素移動后的位置，放進去index = (index + k) % len; //下一次將要移動的元素的下標（即cur替換掉的元素的下標）cur = tmp; //下一次將要移動的元素的值（即被cur覆蓋掉的值）} }

三、整個數(shù)組逆置，再將前半部分和后半部分逆置

思路：{1，2，3，4，5，6，7}移動3個單元格時，{5,6,7}變成前三個元素，{1,2,3,4}變成后四個元素。
第一步：{1，2，3，4，5，6，7}
整個數(shù)組逆置后：{7，6，5，4，3，2，1}
發(fā)現(xiàn)567和1234分別在數(shù)組的前三個和后四個
**第二步：**將前3個再逆置，將后四個再逆置
{5，6，7，1，2，3，4}
完成。
代碼：

//整個數(shù)組的元素逆置，然后將前k個元素逆置，將后len-k個元素逆置 void Reversal_arr(int* arr, int start, int last)//將數(shù)組的下標為[start,last]的元素逆置 {assert(arr != NULL && start <= last);int i = start;int j = last;while (i < j){swap(arr[i++], arr[j--]);} }void Reversal_arr_3(int* arr, int len, int k)//k = 2 {assert(arr != NULL);k = k % len;Reversal_arr(arr, 0, len - 1);//全部逆置Reversal_arr(arr, 0, k - 1); //前k個逆置Reversal_arr(arr, k, len - 1);//后len-k個逆置 }

四、直接找下標移動后對應的下標

思路：直接找下標移動后對應的下標，和第二個方法一樣，只不過第二個方法由于會產(chǎn)生覆蓋問題，所以下一個移動的元素就是上一個被覆蓋的元素，是跳著移動元素。
只不過這里是從前向后一個一個元素的移動，如果直接在原數(shù)組中操作，后面多個元素被覆蓋，所以這里借助輔助空間，都移動到輔助空間中，再拷貝到arr中。這個方法沒有第二個方法好。第二個方法只用了三個多余變量，這個方法用了一個數(shù)組。空間復雜度為O(n)。
代碼：

void Reversal_arr_4(int* arr, int len, int k) {assert(arr != NULL);k = k % len;int* newdata = (int*)malloc(sizeof(int) * len);assert(newdata != NULL);for (int i = 0; i < len; i++){newdata[(i + k) % len] = arr[i];}memcpy(arr, newdata, sizeof(int) * len);delete newdata; }

總結

以上是生活随笔為你收集整理的数组——旋转数组的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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