PAT乙类1008之数组元素循环右移问题一、题目二、代码

140 阅读 0 评论 93 点赞

我是靠谱客的博主温暖冬日，这篇文章主要介绍PAT乙类1008之数组元素循环右移问题一、题目二、代码，现在分享给大家，希望可以做个参考。

一、题目

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
一个数组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

二、代码

方法一：（使用了额外的数组，但是是自己想的）

新的函数
没有
*核心思想

本题中要求向右移动m个位置，我们很容易根据(m+i)%n求出移动后的位置，但是a[i]的元素该何去何从？？
之后我发现，我们只需要将a[0] ~ a[n] 循环移动，(移动后的需要进行标记，不能再移动)，就可以在最后完成移动。
所以需要a[n]来存储数组，b[(m+i)%n]=1来确定是否这个下标的a[(m+i)%n]已经移动过！！

*问题

本题中要求最后不能有空格！！所以需要将最后一个特殊处理

复制代码

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
#include <iostream>
using namespace std;

int main() {
	int a[101];
	int b[101] = {0};
	int i, j = 0, n, m, temp;
	cin>>n>>m;
	for(i=0; i<n; i++) {
		cin>>a[i];
	}  
	for(i=0; i<n; i++) {
		if(b[i] == 0) {
			temp = a[i];
			a[i] = a[(i+m)%n];
			a[(i+m)%n] = temp;
			b[(i+m)%n] = 1;
		}
	}
	for(i=0; i<n; i++) {
		if(i != n-1) {
			cout<<a[i]<< " ";
		}else {
			cout<<a[i];
		}
		
	}
	return 0;

}

方法二：（网上的做法，很精彩）

核心思想

主题思想是，在输入的时候就按照移动过后的进行输入。所以输入 = 移动
同时他也相当于从i=0开始进行的，因为m = （i+m) % n === m = (m++)%n
循环n次，也就将各个值放入了a【n】中

复制代码

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

#include <stdio.h>
 
int main()
{
	int n,m;
	scanf("%d %d",&n,&m);
	if(n<=100&&n>=1){ 
		int temp[n];
		for(int i=0;i<n;i++){
			m=m%n;
			scanf("%d",&temp[m]);
			m++;
		}
		int count=1;
		for(int i=0;i<n;i++){
			printf("%d",temp[i]);
			if(count<n){ 
				printf(" ");
				count++;
			} 
		}
	}
	return 0; 
}