旋转数组的几种做法
创始人
2024-05-29 22:39:54
0

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

 

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

题目描述:

一个数组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
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
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
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;
}

希望老铁们能给点赞赞,感谢! 

相关内容

热门资讯

监控摄像头接入GB28181平... 流程简介将监控摄像头的视频在网站和APP中直播,要解决的几个问题是:1&...
Windows10添加群晖磁盘... 在使用群晖NAS时,我们需要通过本地映射的方式把NAS映射成本地的一块磁盘使用。 通过...
protocol buffer... 目录 目录 什么是protocol buffer 1.protobuf 1.1安装  1.2使用...
在Word、WPS中插入AxM... 引言 我最近需要写一些文章,在排版时发现AxMath插入的公式竟然会导致行间距异常&#...
【PdgCntEditor】解... 一、问题背景 大部分的图书对应的PDF,目录中的页码并非PDF中直接索引的页码...
修复 爱普生 EPSON L4... L4151 L4153 L4156 L4158 L4163 L4165 L4166 L4168 L4...
Fluent中创建监测点 1 概述某些仿真问题,需要创建监测点,用于获取空间定点的数据࿰...
educoder数据结构与算法...                                                   ...
MySQL下载和安装(Wind... 前言:刚换了一台电脑,里面所有东西都需要重新配置,习惯了所...
MFC文件操作  MFC提供了一个文件操作的基类CFile,这个类提供了一个没有缓存的二进制格式的磁盘...