一、题目描述
将一个n(n>1)个整数存放到一维数组R中、设计一个在时间和空间上都尽可能高效的算法,将R中保存的序列循环左移p(0
二、代码实现
首先循环左移p位后新下标的位置为(原下标为i):((i-p)+n)%n,其中n为原数组长度。
0 1 2 3 4 5 6
1 2 3 4 5 6 7 ,循环左移3位:
4 5 6 7 1 2 3 ,原下标为0循环左移3位:((0-3)+7)%7=4,因此下标为4。
接着再开辟一个数组,存放循环后的序列,最后打印即可。相关代码如下:
#include <iostream>
using namespace std;
const int N = 10;
int n, p;
int a[N],b[N];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 0; i < n; i++) { cin >> a[i]; }
cin >> p;
if (p >= n) { cout << "请输入小于n的p值\n"; }
for (int i = 0; i < n; i++)
{
int m=((i - p) + n) % n;//获取新下标值
b[m] = a[i];//将原来的数放在新下标位置
}
for (int i = 0; i < n; i++) { cout << b[i]<<" "; }
return 0;
}
显然该算法的时间复杂度和空间复杂度均为O(N);
三、总结
本题较为简单,注意循环左移后新下标与原下标的对应关系是:
m=((i-p)+n)%n
- THE END -
最后修改:2024年2月3日