首页 > 试题广场 >

数组元素循环右移问题 (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

算法知识视频讲解

Java

已注销

有一个老哥说得对，不用去翻转数组，只要保证输出的顺序就可以了.....

import java.util.Iterator;
import java.util.Scanner;
import java.util.TreeSet;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuffer sb = null;
        while (sc.hasNext()) {
            sb = new StringBuffer();
            int n = sc.nextInt();
            int m = sc.nextInt();
            m = m % n;
            for (int i = 0; i < n - m; i++) {
                if(i == n - m - 1){
                    sb.append(sc.nextInt());
                } else {
                    sb.append(sc.nextInt() + " ");
                }
            }
            for (int i = 0; i < m; i++) {
                System.out.printf(sc.nextInt() + " ");
            }
            System.out.println(sb.toString());
        }
    }
}

编辑于 2017-10-09 15:15:06 回复(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)