一 、问题描述
将长度为n的整形数组A进行右移m位操作, [A0 A1 A2 A3 ... Am...An-1]变为[An-m...An-1 A0 A1 A2 A3 ...An-m-1 ]
输入格式:
每个输入包含一个测试用例,第1行输入N(>0)和M(>=0);第2行输入N个整数,之间用空格分隔。
输出格式:
在一行中输出循环右移M位以后的整数序列,之间用空格分隔,序列结尾不能有多余空格。
输入样例:
6 2
1 2 3 4 5 6
输出样例:
5 6 1 2 3 4
二、解题思路
比较常用的思路就是逆序打印再正序打印,和三次逆序翻转。
显然翻转操作解题更符合题意,通过三次翻转操作,可得到右移的数组。首先对数组A整体进行翻转,然后再对A[0]到A[m-1]进行翻转,最后再对A[m]到A[n-1]这部分进行翻转操作,最后得到右移效果。
下图为n= 10, m = 4的例子:
解题代码如下:
#include <stdio.h> void printMove( int A[], int arraySize )
{
int j;
for ( j = ; j < arraySize; j++ ) {
printf("%d", A[j]);
if ( j < (arraySize - ) ) {
printf(" ");
}
}
} void move( int A[], int left, int right)
{
while ( left < right ) {
int temp = A[left];
A[left] = A[right];
A[right] = temp; left++;
right--;
}
} void move_A( int A[], int left, int right )
{ // 从左到右进行元素交换
int i, mid, tmp; mid = ( right - left + ) / ;
for ( i = ; i < mid; i++ ) {
tmp = A[i + left];
A[i + left] = A[right - i];
A[right - i] = tmp;
}
} int main(int argc, char *argv[])
{
int i, j;
int arraySize, moveStep;
scanf("%d %d", &arraySize, &moveStep); int A[arraySize];
for ( i = ; i < arraySize; i++ ) {
scanf("%d", &A[i]);
//A[i] = i+1;
} /* three step */
if ( moveStep > ) {
moveStep = moveStep % arraySize;
move( A, , arraySize - );
//printMove( A, arraySize ); printf("\n"); move( A, , moveStep - );
//printMove( A, arraySize ); printf("\n"); move( A, moveStep, arraySize - );
printMove( A, arraySize ); //printf("\n");
} else {
printMove( A, arraySize ); //printf("\n");
} return ;
}
Python版本:
nums = input()
L = nums.split(" ")
A, B = int(L[0]), int(L[-1])
B = B % A numChars = input().split(" ")
Array = [ int(i) for i in numChars ] if B > 0:
Array = Array[::-1]
leftA = Array[:B][::-1]
rightA = Array[B:][::-1]
Array = leftA + rightA length= len(Array)
for i in range(length):
print( Array[i], end="")
if i < (length - 1):
print( " ", end="")
i = i + 1