题解

本题可以使用 数组翻转法 实现高效右移操作，避免暴力方法导致的 O(n*k) 超时问题。

解法：数组翻转

思路

1. 先翻转整个数组

   ：

   • 例：[1,2,3,4,5,6,7] 变成 [7,6,5,4,3,2,1]

2. 翻转前 k 个元素

   ：

   • [7,6,5] 变成 [5,6,7]

3. 翻转剩余 n-k 个元素

   ：

   • [4,3,2,1] 变成 [1,2,3,4]

4. 最终结果

   ：

   • [5,6,7,1,2,3,4]

时间复杂度

• 翻转数组三次，每次 O(n)，所以总时间复杂度是 O(n)，空间复杂度 O(1)。

代码实现

C++ 实现

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void rotateArray(vector<int>& nums, int k) {
    int n = nums.size();
    k = k % n;  // 避免 k 过大
    reverse(nums.begin(), nums.end());  // 翻转整个数组
    reverse(nums.begin(), nums.begin() + k);  // 翻转前 k 个元素
    reverse(nums.begin() + k, nums.end());  // 翻转后 n-k 个元素
}

int main() {
    int n, k;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    cin >> k;
    
    rotateArray(nums, k);
    
    for (int i = 0; i < n; i++) {
        cout << nums[i] << " ";
    }
    cout << endl;

    return 0;
}

Python 实现

def rotate_array(nums, k):
    """
    旋转数组
    """
    n = len(nums)
    k %= n  # 避免 k 超过 n
    nums.reverse()  # 翻转整个数组
    nums[:k] = reversed(nums[:k])  # 翻转前 k 个元素
    nums[k:] = reversed(nums[k:])  # 翻转后 n-k 个元素

if __name__ == "__main__":
    n = int(input())
    nums = list(map(int, input().split()))
    k = int(input())

    rotate_array(nums, k)
    print(" ".join(map(str, nums)))

Java 实现

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void rotateArray(int[] nums, int k) {
        int n = nums.length;
        k %= n;  // 避免 k 超过 n
        reverse(nums, 0, n - 1);  // 翻转整个数组
        reverse(nums, 0, k - 1);  // 翻转前 k 个元素
        reverse(nums, k, n - 1);  // 翻转后 n-k 个元素
    }

    private static void reverse(int[] nums, int left, int right) {
        while (left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        int k = scanner.nextInt();
        scanner.close();

        rotateArray(nums, k);

        for (int num : nums) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

题目描述

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

输入格式

• 第一行输入整数 n，表示数组 nums 的长度。
• 第二行输入 n 个整数，表示数组 nums 的元素。
• 第三行输入一个整数 k，表示右移的步数。

输出格式

• 输出 n 个整数，表示 nums 右移 k 步后的结果。

输入样例

7
1 2 3 4 5 6 7
3

输出样例

5 6 7 1 2 3 4

说明

向右轮转 1 步: [7,1,2,3,4,5,6]

向右轮转 2 步: [6,7,1,2,3,4,5]

向右轮转 3 步: [5,6,7,1,2,3,4]