旋转数组的几种做法

千淘万浪虽辛苦，吹尽黄沙始到金。                           ——刘禹锡

 

第一种方法：遍历整个数组

题目描述：

一个数组A中存有N (N>0) 个整数，允许使用另外数组，将每个整数循环向右移动M(M>=0)个位置。如果需要考虑程序移动数据的次数尽量少，要如何设计移动的方法?
输入说明:第1行输入N (1<=N<=100)、M (M>=0) ，第2行输入N个整数。
输出说明:输出循环右移M位以后的整数序列。
旋转数组_牛客题霸_牛客网 (nowcoder.com)

实例：

输入：6,2,[1,2,3,4,5,6]

返回值：[5,6,1,2,3,4]

输入：4,0,[1,2,3,4]

返回值：[1,2,3,4]

这里我们就把旋转数组的几种方法全部写出来，先不考虑程序移动数据的次数尽量少。

第一种方法：遍历整个数组

当我们输入5 ，3时，也就是5个数字，移动3个数字。

这个方法就是要移动3个数字，就要移动3次，1次移动一个数字。

比如：

当输入1  2  3  4  5时，我们第1次就把5依次的和前面的数字进行交换，交换一次就是1  2  3  5  4，然后5又和前面的数字进行交换，以此类推，最终把5交换到最前面，也就是 5  1  2  3  4。

这里我们还要考虑一个问题，当n的输入值大于m的值时，应该怎么移？我们知道当n和m的值一样的话，数组就不变。那如果m的输入值大于n的值时，我们只需要移动m%n次就够了，其实无论谁大谁小，移动m%n次就够了。

就这样一次一次的移动数字，最终达到我们想要的效果。

void rorate_arr(int* arr, int n, int m)
{int i = 0;int j = 0;m = n % m;for (i = 0; i < m; i++)//一共m次{for (j = n - 1; j > 0; j--)//五个数一共交换四次{//这个循环是一次交换好一个数字int temp = arr[j];arr[j] = arr[j - 1];arr[j - 1] = temp;}}
}
int main()
{int arr[100] = { 0 };int n = 0;int m = 0;int i = 0;scanf("%d %d", &n, &m);for (i = 0; i < n; i++){scanf("%d", &arr[i]);}rorate_arr(arr, n, m);for (i = 0; i < n; i++){printf("%d ", arr[i]);}return 0;
}

---

 

第二种方法： 按目的打印出来就行

#include<stdio.h>
int main()
{int arr[100] = { 0 };int n = 0;int m = 0;int i = 0;int j = 0;scanf("%d %d", &n, &m);for (i = 0; i < n; i++){scanf("%d", &arr[i]);}int sum = m % n;for (j = sum - 1; j >= 0; j--)//打印要移动的那几个数{printf("%d ", arr[n - j - 1]);}for (j = 0; j < n - sum; j++)//打印不移动那几个数{printf("%d ", arr[j]);}return 0;
}

#include<stdio.h>
void rorate_arr(int* arr, int n, int m)
{int i = 0;int j = 0;for (i = 0; i < n; i++){scanf("%d", arr + i);}m = m % n;for (j = 0; j < n; j++){printf("%d ",arr[(n-m+j)%n]);//如果n-m+j的值大于等于n时，开始打印不移动的数。}
}
int main()
{int arr[100] = { 0 };int n = 0;int m = 0;scanf("%d %d", &n, &m);rorate_arr(arr, n, m);return 0;
}

 第三种方法：先逆序m个数字，再逆序n-m个数字，再整体逆序。

实例：输入5，3，一共5个数字，3个数字旋转。当输入1 2 3 4 5时，我们就先可以把3 4 5的三个数字进行逆序，也就是变成5 4 3，再把1 2进行逆序，变成2 1。得到了2 1 5 4 3，然后再全部逆序一遍成3 4 5 1 2，也就得到我们想要的顺序了。

#include<stdio.h>
void reverse_arr(int*arr, int left,int right)
{while (left < right)//当左下标小于右下标时，就发生交换{int temp = arr[left];arr[left] = arr[right];arr[right] = temp;left++;right--;}
}
void rorate_arr(int* arr, int n, int m)
{m = m % n;reverse_arr(arr, n - m,n-1);//m个数字进行逆序reverse_arr(arr, 0, n-m-1);//n-m个数字进行逆序reverse_arr(arr, 0, n-1);//整体逆序int i = 0;for (i = 0; i < n; i++){printf("%d ", arr[i]);}
}
int main()
{int arr[100] = { 0 };int i = 0;int n = 0;int m = 0;scanf("%d %d", &n, &m);for (i = 0; i < n; i++){scanf("%d", &arr[i]);}rorate_arr(arr, n, m);return 0;
}

希望老铁们能给点赞赞，感谢！