一个数组A中存有N(>0)个整数,在不允许使用另外数组的前提下,将每个整数循环向右移M(≥0)个位置,即将A中的数据由($A_0 A_1⋯A_{N−1}$)变换为($A_{N-M}⋯A_{N−1} A_0 A_1⋯A_{N−M−1}$)(最后M个数循环移至最前面的M个位置)。如果需要考虑程序移动数据的次数尽量少,要如何设计移动的方法?
输入格式:
每个输入包含一个测试用例,第1行输入N(1≤N≤100)和M(≥0);第2行输入N个整数,之间用空格分隔。
输出格式:
在一行中输出循环右移M位以后的整数序列,之间用空格分隔,序列结尾不能有多余空格。
输入样例:
1 | 6 2 |
输出样例:
1 | 5 6 1 2 3 4 |
解法一:直接法
算法思路:每次向右移动一位,循环执行m次
代码实现
1 |
|
- 时间复杂度:每次向右移动一位,需要执行n次赋值操作,这个过程循环执行m次,所以共执行nm次赋值操作,时间复杂度为O(nm)
解法二:反转法
- 算法思想
假设N>=M(若N<M,只需令M=M%N即可),数组A中的数据为$A_0 A_1⋯A_{N−1}$,现在需要将数组A循环向右移M个位置,即将$A_{N-M}⋯A_{N−1}$移到数组的前面。
我们可以将数组A中的数据分为两个部分$A_0 A_1⋯A_{N−M-1}$和$A_{N-M}⋯A_{N−1}$来看,
(1)先将$A_0 A_1⋯A_{N−M-1}$反转,得到$A_{N−M-1} ⋯A_1 A_0$;
(2)再将$A_{N-M}⋯A_{N−1}$反转,得到$A_{N-1}⋯A_{N−M}$
(3)经过(1)和(2)后,数组A中的数据为$A_{N−M-1} ⋯A_1 A_0 A_{N-1}⋯A_{N−M}$,将数组A中的数据反转,此时数组A中的数据顺序为$A_{N-M}⋯A_{N−1} A_0 A_1⋯A_{N−M−1}$
- 代码实现
1 |
|
- 时间复杂度
三次反转操作,共执行 $3 \times \frac{n-m}{2}+3 \times [n-\frac{m}{2}-(n-m)]+3 \times \frac{n}{2}=3n$次赋值操作,故时间复杂度为O(n)