Fork me on GitHub
0%

数组元素循环右移问题

一个数组A中存有N(N&gt0)个整数,在不允许使用另外数组的前提下,将每个整数循环向右移M(M>=0)个位置,即将A中的数据由(A0 A1 ……AN-1 )变换为(AN-M …… AN-1 A0 A1 ……AN-M-1 )(最后M个数循环移至最前面的M个位置)。如果需要考虑程序移动数据的次数尽量少,要如何设计移动的方法?要求时间复杂度为O(N),且只允许使用两个附加变量

输入描述:

每个输入包含一个测试用例,第1行输入N ( 1<=N<=100)、M(M>=0);第2行输入N个整数,之间用空格分隔。

输出描述:

在一行中输出循环右移M位以后的整数序列,之间用空格分隔,序列结尾不能有多余空格。

示例1
输入

1
2
6 2
1 2 3 4 5 6

输出

1
5 6 1 2 3 4

假设原数组序列为abcd1234,要求变换成的数组序列为1234abcd,即循环右移了4位。比较发现,其中两段的顺序是不变的,1234和abcd,可以把这两段看成两个整体。右移k位的过程就是把数组两部分交换一下,交换过程可以通过三次反转实现:

1.反转前k部分:abcd1234->dcba1234;
2.反转后面部分:dcba1234->dcba4321;
3.整体反转:dcba4321->1234abcd

move-elements-in-array-cyclically.cpplink
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
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void print_vec(vector<int> &nums)
{
for (int i = 0; i < nums.size(); i++)
{
if (i == nums.size() - 1)
cout << nums[i] << endl;
else
cout << nums[i] << " ";
}
}

void move(vector<int> &nums, int M)
{
M = M % nums.size();
reverse(nums.begin(), nums.begin() + nums.size() - M);
// print_vec(nums);
reverse(nums.begin() + nums.size() - M, nums.end());
// print_vec(nums);
reverse(nums.begin(), nums.end());
}

int main(int argc, char const *argv[])
{
int N, M;
cin >> N >> M;
vector<int> nums(N, 0);
for (int i = 0; i < N; i++)
{
cin >> nums[i];
}
move(nums, M);
print_vec(nums);
return 0;
}

Link
Send
Send
Pin
打赏一次,年薪百万.