首页 > 试题广场 >

数组元素循环右移问题 (20)

[编程题]数组元素循环右移问题 (20)

热度指数：4754 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

一个数组A中存有N（N&gt0）个整数，在不允许使用另外数组的前提下，将每个整数循环向右移M（M>=0）个位置，即将A中的数据由（A₀ A₁ ……A_N-1 ）变换为（A_N-M …… A_N-1 A₀ A₁ ……A_N-M-1 ）（最后M个数循环移至最前面的M个位置）。如果需要考虑程序移动数据的次数尽量少，要如何设计移动的方法？

输入描述:

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

输出描述:

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

示例1

输入

6 2
1 2 3 4 5 6

输出

5 6 1 2 3 4

算法知识视频讲解

陈年风楼


	#include<stdio.h>
 
 //交换函数:用于交换from 和 end 所指向的值,这个函数的功能就是
 //反转从from到end的这个数列 
void Swap(int a[], int from, int end)
{
    while(from<end){
        a[from]^= a[end]^= a[from]^= a[end];
        from++;
        end--;
    }
}

int main(void)
{
    int M,N;
    scanf("%d",&N);
    scanf("%d",&M);
    int a[N];
    int m= M%N; 
    for(int i= 0; i< N; i++)
        scanf("%d",a+i);
    Swap(a,0,N-1);//先整体翻转过来使数列倒序 
    Swap(a,0,m-1);//然后部分翻转实现循环右移 
    Swap(a,m,N-1);
    for(int i= 0; i< N-1; i++)
        printf("%d ",a[i]);
    printf("%d",a[N-1]);//最后一个数字后不能有空格,害我找了好久的错误,就说么,哪儿出错了
     
}

发表于 2015-12-06 22:41:55 回复(2)

C/C++

Caffeine

思路：输入的时候就按照移序的方式输入。然后正常输出就可以了。牛逼吧！
#include <iostream>
using namespace std;

int main()
{
    int n, m;
    while (cin >> n >> m)
    {
        int * a = new int[n];
        m = m % n;
        for (int i = 0,j = m; i < n; i++,j++)
        {
            if (j > n - 1)
            {
                j = 0;
            }
            cin >> a[j];
        }
        for (int i = 0; i < n; i++)
        {
            if(i != n-1)
                cout << a[i] << " ";
            else
            {
                cout << a[i] << endl;
            }
        }
    }
}

发表于 2018-08-13 22:00:02 回复(1)

STEVE1104

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int N = in.nextInt(), M = in.nextInt();
		int count = 0;
		int[] A = new int[N];
		M = M % N;//M可能比N大
		for (int i = 0; i < N; i++) {
			A[i]=in.nextInt();
		}
		for(int i=N-M;i<N;i++)
		{
			System.out.print(A[i]);
			count++;
			if(count<N)
			{
				System.out.print(" ");
			}
		}
		for(int  i=0;i<N-M;i++)
		{
			System.out.print(A[i]);
			count++;
			if(count<N)
			{
				System.out.print(" ");
			}
		}

	}

}

* 题目并不关心怎么移动，只关心输出！只要先从N-M号元素到N-1号元素，再输出1到N-M-1即可；

编辑于 2016-09-25 15:52:33 回复(2)

C/C++

Jino.


        #include

        #include

        using namespace std;

        int main(){

        int a[110];

        int n,m;

        cin>>n>>m;

        int count=0;

        m=n%m;//确定移动位数

        for(int i=0;in;i++){

        cin>>a[i];

        }

        for(int i=n-m;in;i++){

        couta[i];

        count++;

        if(countn)cout" ";

        }

        for(int i=0;in-m;i++){

        couta[i];

        count++;

        if(countn)cout" ";

        }

        return 0;

        }

编辑于 2018-11-16 11:18:39 回复(0)

kestars

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        ArrayList<Integer> list=new ArrayList<Integer>();
        ArrayList<Integer> result=new ArrayList<Integer>();
        for(int i=0;i<n-m%n;i++){
            list.add(sc.nextInt());
        }
        for(int i=0;i<m%n;i++){
            result.add(sc.nextInt());
        }
        result.addAll(list);
        for(int i=0;i<result.size()-1;i++){
            System.out.print(result.get(i)+" ");
        }
        System.out.print(result.get(result.size()-1));
    }
}

发表于 2018-10-02 10:10:00 回复(0)

Python

字节电商

  N,M=map(int,input().split(' ')) 
  l=list(map(int,input().split(' '))) 
  r=M%N 
  for i in range(-r,N-r): 
        if i==N-r-1: 
            print(l[i]) 
        else: 
            print(l[i],end=' ') 

发表于 2018-05-12 01:02:44 回复(0)

Java

Old_dream

java版，复杂度 O(N）。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

// complexity O(N)
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        int N = 0, M = 0;
        int[] A = null;
        for (int i = 0; i < 2; i++) {
            if (i == 0) {
                String[] temp = input.readLine().split("\\s");
                N = Integer.parseInt(temp[0]);
                M = Integer.parseInt(temp[1]);
            }
            else {
                String[] temp = input.readLine().split("\\s");
                A = new int[N];
                for (int j = 0; j < N; j++) {
                    A[j] = Integer.parseInt(temp[j]);
                }
            }
        }
        input.close();
        A = moveA(A, M);
        printer(A);
    }

    private static int[] moveA(int[] A, int M) {
        M %= A.length;
        if (M == 0)
            return A;
        reverse(A, 0, A.length - 1);
        reverse(A, 0, M - 1);
        reverse(A, M, A.length - 1);
        return A;
    }

    // reverse array from start to end
    private static void reverse(int[] a, int start, int end) {
        for (int i = start, j = end; i <= (start + end) / 2; i++, j--) {
            swap(a, i, j);
        }
    }

    private static void swap(int[] a, int left, int right) {
        int temp = a[left];
        a[left] = a[right];
        a[right] = temp;
    }

    private static void printer(int[] A) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < A.length; i++) {
            sb.append(A[i]);
            sb.append(" ");
        }

        sb.deleteCharAt(sb.length() - 1);
        System.out.println(sb.toString());
    }
}

编辑于 2017-09-12 12:16:15 回复(0)

Python

questRush

from collections import deque
try:
    while 1:
        n, m = map(int, raw_input().split())
        L = deque(raw_input().split())
        L.rotate(m)
        print ' '.join(L)
except:
    pass

发表于 2017-01-17 11:38:45 回复(1)

战斗啊阿西吧

在录入数据时，按题意排好顺序，然后输出即可。

#include<stdio.h>
int main( void )
{
    int n, right;
    scanf("%d %d",&n, &right );

    int i;
    int num[ 100 ];
    for( i = 0; i < n; i++ ){
        right = right % n;
        scanf("%d", &num[ right ] );
        right++;
    }

    for( i = 0; i < n - 1; i++ ){
        printf("%d ", num[ i ] );
    }
    printf("%d\n", num[ i ] );

    return 0;
}

发表于 2016-02-26 11:52:32 回复(1)

Thkeer

import java.util.Scanner;

class rightM{
	public int[] aryN;
	public void inputMove(){
		int n = 0; 
		int step = 0;
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		aryN = new int[n];
		step = sc.nextInt();
		for(int i=step%n;i<n;i++){
			aryN[i] = sc.nextInt();
		}
		for(int i=0;i<step%n;i++){
			aryN[i] = sc.nextInt();
		}
		for(int i=0;i<n;i++){
			System.out.print(""+aryN[i]);
			if(i!=n-1) 
				System.out.print(" ");
		}
	}
}

public class Main {
	public static void main(String[] args){
		rightM rm = new rightM();
		rm.inputMove();
	}
}

不移动数组，在输入的时候排好位置就好。

发表于 2016-02-07 00:44:33 回复(0)

Python

华科平凡

python solution：

a, b = map(int, input().split())
c = input().split()
if b % a == 0:
    print(" ".join(c))
else:
    print(" ".join((c[-b % a:] + c[:a - b % a])) if a > 1 else c[0])

编辑于 2018-12-04 06:01:13 回复(1)

LuxSun

// 秒杀技巧：先取mod，然后在输入的时候就把位置移好！
// （跳出惯性思维，一般人会觉得先把数据录好再移位）
// 最后的输出也别具一格，哈哈~
// 希望可以采纳~
import java.util.Arrays;
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while(in.hasNext()){
			int n=in.nextInt(),m=in.nextInt();
			m%=n;
			int[] arr=new int[n];
			for (int i = 0,k=0; i < n; i++) {
				if(i+m<n){
					arr[i+m]=in.nextInt();
				}
				else{
					arr[k++]=in.nextInt();
				}
			}
			System.out.println(Arrays.toString(arr).replaceAll("\\[|\\]|,", ""));
		}
	}
}

发表于 2017-08-09 09:27:11 回复(6)

C/C++

猫猫猫1

#include<bits/stdc++.h>
using namespace std;

const int Max=10010;
int a[Max];

int main(){
	int n,m;
	while(cin>>n>>m){
        m=m%n;
		for(int i=0;i<n;i++){
			cin>>a[i];
		}
		for(int i=n-1;i>=0;--i){
			a[m+i]=a[i];
		}
		for(int i=m-1;i>=0;--i){
			a[m-1-i]=a[n+m-1-i];
		}
		for(int i=0;i<n;i++){
			cout<<a[i];
			if(i<n-1) cout<<" ";
		}
		cout<<endl;
	}
	return 0;
}

发表于 2022-11-02 16:45:35 回复(1)

C/C++

来个offer吧ball

#include <iostream>

using namespace std;

const int SIZE = 100;

int main() {
    int N, M;
    cin >> N >> M;
    if (M >= N)
        M = M % N;
    int array[SIZE];
    for (int i = 0; i < N; ++i) {
        cin >> array[i];
    }
    for (int i = 0; i < M; ++i) {
        int tem = array[N - M + i];
        for (int j = N - M + i; j > i; --j) {
            array[j] = array[j - 1];
        }
        array[i] = tem;
    }
    cout << array[0];
    for (int i = 1; i < N; ++i) {
        cout << " " << array[i];
    }
    cout << endl;
    return 0;
}

发表于 2021-04-05 11:52:54 回复(0)

杨豪好好找工作

//直接按结果输入hh
#include<iostream>
using namespace std;

int arr[110];

int main(){
    int n, k;
    while(cin>>n>>k){
        for(int i=k%n; i<n; i++){
            cin>>arr[i];
        }
        for(int i=0; i<k%n; i++){
            cin>>arr[i];
        }
        for(int i=0; i<n; i++){
            if(i==n-1){
                cout << arr[i] << endl;
            } else {
                cout << arr[i] << " ";
            }
        }
    }
    return 0;
}

发表于 2021-03-24 22:16:21 回复(0)

阿Q想offer

#include <iostream>
using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
    int a[n];
    for(int i=0; i<n; i++)
    {
        cin>>a[(i+m)%n];
    }
    for(int i=0; i<n; i++)
        if(i!=n-1)
            cout<<a[i]<<" ";
        else
            cout<<a[i];
    return 0;
}

发表于 2020-08-25 09:35:28 回复(0)

思晓

#include <stdio.h>
(737)#include <algorithm>  //reverse()  左闭右开

using namespace std;

int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    m%=n;  //m可能大于n
    int a[n];
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    reverse(a,a+n);
    reverse(a,a+m);
    reverse(a+m,a+n);  //左闭右开
    for(int i=0;i<n;i++)
    {
        printf("%d",a[i]);
        if(i!=n-1)
            printf(" ");
    }
    return 0;
}

发表于 2020-04-12 15:49:00 回复(0)

hestyle

$\color{blue}解题思路：$
这道题最常规的解法是手动去移动，但这显然体现不出算法的伟大。下面介绍两种较为高效的方法：

方法一：翻转法

所谓翻转法，就是分别将[0, n - 1]、[0, m - 1]、[m, n - 1]翻转。
比如对于n = 7，m = 2，[1 2 3 4 5 6]
先翻转区间[0, n - 1]，得到[6 5 4 3 2 1]
再翻转区间[0, m - 1]，得到[5 6 4 3 2 1]
最后翻转区间[m, n - 1]，得到[5 6 1 2 3 4]

三次翻转得到的最终结果就是向右循环移动两次的结果。

方法二：辅助队列法（链表）

稍微知道一点数据结构的都知道队列这种数据结构，先进先出的特性。只要把队头的元素出队、再入队（队尾），重复n - m次。
比如对于n = 7，m = 2，队列[1 2 3 4 5 6]
队头放入队尾 [2 3 4 5 6 1]
队头放入队尾 [3 4 5 6 1 2]
队头放入队尾 [4 5 6 1 2 3]
队头放入队尾 [5 6 1 2 3 4]

4次出队、入队操作得到的最终结果就是向右循环移动两次的结果。
如果你还知道有一种双端队列（队头、队尾都可以进行出队、入队操作）的数据结构，
其实对于这种情况只需要2次把队尾放入队头就行。
当然你也可以手动构造一个链表，将链表的头部放入链表的尾部

$\color{red}注意：$ 循环移动移动n次与不移动的是一样的，所以当m > n时可以缩减移动次数m %= n。

$\color{blue}代码实现：$
移动规律——翻转法

#include <iostream>
(720)#include <cstring>
using namespace std;

int main() {
    int n = 0, m = 0, tempNum, numbers[101] = {0};
    //primerTable[i]记录i是否是素数
    while (scanf("%d %d", &n, &m) != EOF) {
        m %= n;//移动n次与不移动是一样的
        //获取输入的数组
        for (int i = 0; i < n; ++i) {
            scanf("%d", numbers + i);
        }
        //将[0, n - 1]区间翻转
        for (int left = 0, right = n - 1; left < right; ++left, --right) {
            tempNum = numbers[left];
            numbers[left] = numbers[right];
            numbers[right] = tempNum;
        }
        //将[0, m - 1]区间翻转
        for (int left = 0, right = m - 1; left < right; ++left, --right) {
            tempNum = numbers[left];
            numbers[left] = numbers[right];
            numbers[right] = tempNum;
        }
        //将[m, n - 1]区间翻转
        for (int left = m, right = n - 1; left < right; ++left, --right) {
            tempNum = numbers[left];
            numbers[left] = numbers[right];
            numbers[right] = tempNum;
        }
        for (int i = 0; i < n - 1; ++i) {
            printf("%d ", numbers[i]);
        }
        printf("%d\n", numbers[n - 1]);
    }
    return 0;
}
————————————————
版权声明：本文为CSDN博主「hestyle」的原创文章，遵循 CC 4.0 BY 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://hestyle.blog.csdn.net/article/details/104761085

数据结构——队列（链表）

#include <iostream>
(720)#include <queue>
using namespace std;

int main() {
    int n = 0, m = 0, tempNum;
    //primerTable[i]记录i是否是素数
    while (scanf("%d %d", &n, &m) != EOF) {
        queue<int> myQue;//辅助队列，注意这是平常的单端队列，只能从队头出队，队尾入队，并不是双端队列deque
        for (int i = 0; i < n; ++i) {
            scanf("%d", &tempNum);
            myQue.push(tempNum);
        }
        //循环右移n次与不移动的效果是一样的
        m %= n;
        //连续操作n - m次，将队头放入队尾
        for (int i = n - m; i > 0; --i) {
            //将队头放入队尾
            myQue.push(myQue.front());
            myQue.pop();
        }
        //输出结果
        for (int i = n - 1; i > 0; --i) {
            printf("%d ", myQue.front());
            myQue.pop();
        }
        printf("%d\n", myQue.front());
        myQue.pop();
    }
    return 0;
}
————————————————
版权声明：本文为CSDN博主「hestyle」的原创文章，遵循 CC 4.0 BY 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://hestyle.blog.csdn.net/article/details/104761085

发表于 2020-03-09 21:24:10 回复(0)

C/C++

不偷不抢安度因_

//三次翻转
#include <stdio.h>
#include <stdlib.h>
 
void reverse(int*, int, int);
 
int main()
{
    int m, n;
    while(~scanf("%d %d", &n, &m))
    {
        m = m % n;
        int s[100] = {0};
        int i;
        for(i = 0; i < n; i++)
            scanf("%d", s + i);
        reverse(s, 0,     n - m - 1);
        reverse(s, n - m, n - 1);
        reverse(s, 0,     n - 1);
        for(i = 0; i < n; i++)
        {
            if(i == 0)
                printf("%d", s[i]);
            else
                printf(" %d", s[i]);
        }
        printf("\n");
    }
 
    return 0;
}
 
void reverse(int s[], int start, int end)
{
    for(int i = 0; i < (end - start + 1) / 2; i++)
    {
        int temp = s[start + i];
        s[start + i] = s[end - i];
        s[end - i] = temp;
    }
}

编辑于 2020-03-04 21:15:16 回复(0)

Finalize

这个题最最坑比的地方在于它移位的测试数据是可能会大于数组长度的，虽然输入限制里有范围但是还是容易造成思维误区，没有考虑这个问题而无法通过。解决方式也是很简单，对移动的move对数组长度len取一次mod即可

整体思路：三次翻转思想，以移动的步长为分割线，从右往左找到第len-move元素分成两部分，分别对左边翻转一次，右边翻转一次，最后整体翻转一次就是答案了

比如：

输入：6 2

数组内容是：1 2 3 4 5 6
第一次翻转：4 3 2 1 5 6
第二次翻转：4 3 2 1 6 5
第三次翻转：5 6 1 2 3 4

#include<bits/stdc++.h>
using namespace std;
void reverse(int a[],int start,int end){
    for(int i=start;i<=(end+start)/2;i++){
        int temp=a[i];
        a[i]=a[end-i+start];
        a[end-i+start]=temp;
    }
}
int main(){
   int len,move;
    while(~scanf("%d %d",&len,&move)){
        int a[105];
        for(int i=0;i<len;i++)scanf("%d",&a[i]);
        move%=len;
        reverse(a,0,len-(move+1));      
        reverse(a,len-move,len-1);      
        reverse(a,0,len-1);
        for(int i=0;i<len-1;i++)printf("%d ",a[i]);
        printf("%d",a[len-1]);
        printf("\n");
    }
    return 0;
}

发表于 2020-02-07 14:32:53 回复(0)