轮转数组

题意

将数组右移 k 步，原地修改。

思路

暴力每次移动一位 O(nk)。三次反转法 O(n) 时间 O(1) 空间：先整体反转，再反转前 k 个，再反转后 n-k 个。原理：右移 k 步相当于把后 k 个元素移到前面。

也可以用额外数组存结果再复制回来 O(n) 空间。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31/**
 * Author by Rainboy
 */
// main.cpp：三次反转，O(n) 时间 O(1) 空间。
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    void rotate(vector<int> &nums, int k) {
        int n = nums.size();
        k %= n;
        reverse(nums.begin(), nums.end());
        reverse(nums.begin(), nums.begin() + k);
        reverse(nums.begin() + k, nums.end());
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int &x : a)
        cin >> x;
    Solution().rotate(a, k);
    for (int x : a)
        cout << x << ' ';
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22#!/usr/bin/env python3
from typing import List


class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        n = len(nums)
        k %= n
        nums.reverse()
        nums[:k] = reversed(nums[:k])
        nums[k:] = reversed(nums[k:])


def main() -> None:
    n, k = map(int, input().split())
    nums = list(map(int, input().split()))
    Solution().rotate(nums, k)
    print(*nums)


if __name__ == "__main__":
    main()

复杂度

时间复杂度：O(n)，每个元素被反转两次。
空间复杂度：O(1)。

总结

三次反转是"分段交换"的经典手法。类似思路也用于单词反转、循环移位等场景。

目录

题意

思路

代码

复杂度

总结