题目
一个数组A中存有N(>0)个整数,在不允许使用另外数组的前提下,将每个整数循环向右移M(≥0)个位置,即将A中的数据由(A0A1⋯AN−1)变换为(AN−M⋯AN−1A0A1⋯AN−M−1)(最后M个数循环移至最前面的M个位置)。如果需要考虑程序移动数据的次数尽量少,要如何设计移动的方法?
输入格式:
每个输入包含一个测试用例,第1行输入N(1≤N≤100)和M(≥0);第2行输入N个整数,之间用空格分隔。
输出格式:
在一行中输出循环右移M位以后的整数序列,之间用空格分隔,序列结尾不能有多余空格。
输入样例:
6 2
1 2 3 4 5 6
输出样例:
5 6 1 2 3 4
思路
首先,将偏移量缩减到n以内:offset %= n;
然后,考虑只申请1个额外空间,每次移动1个元素,则有:
循环n与offset的最大公约数次就能遍历到所有元素。(需注意offset可能为0)
例如6/4,要遍历所有元素需2次循环(0-4-2,1-5-3);每个循环的终止条件是又回到起始位置。
(也有取巧的方法,如直接按偏移后的位置输入,或直接根据偏移量输出,不做真正意义上的移动,)
算法
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55#include <iostream> #include <vector> using namespace std; void PrintArray(vector<int> a);//打印数组 void PrintArray(vector<int> a) { vector<int>::iterator it=a.begin(); cout << *it; it++; while (it!=a.end()){ cout << " " << *it; it++; } cout<<endl; } //注意offset可能为0 int GCD(int a, int b){ if (a==0||b==0){ return 0; } int m = a%b; while (m!=0){ a = b; b = m; m = a%b; } return b; } int main(){ int n; int offset; cin >> n >> offset; offset %= n; vector<int> a(n); for (int i=0; i<n; i++){ cin >> a[i]; } //循环n与offset的最大公约数次就能遍历到所有元素 int loops = GCD(n, offset); for (int i=0; i<loops; i++){ int start = i; //只申请2个额外空间,谁腾地方,下一个就移动谁。 int cur = a[i]; int next; int pos = i; do { pos = (pos + offset) % n; next = a[pos]; a[pos] = cur; cur = next; }while (pos!=start); } PrintArray(a); return 0; }
最后
以上就是繁荣路人最近收集整理的关于PAT乙级真题 1008 数组元素循环右移问题 C++实现的全部内容,更多相关PAT乙级真题内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复