leetcode189：旋转数组

题目链接

leetcode

题目描述

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

C++ 代码

#include <iostream>
#include <vector>
using namespace std;

/*
    使用额外的数组，将每个元素放至正确的位置。
    遍历原数组，将下标为 i 的元素放到新数组下标为 (i+k) % n 的位置，
    最后将新数组拷贝到原数组。

    时间复杂度：O(n)
    空间复杂度：O(n)
*/
class Solution_0 {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> temp(n);

        for (int i = 0; i < n; i++) {
            temp[(i+k) % n] = nums[i];
        }

        nums.assign(temp.begin(), temp.end());
    }
};

/*
    先将所有元素翻转，尾部的 k % n 个元素就被移至数组头部，
    然后再翻转 [0, k%n−1] 元素和 [k%n, n-1] 元素，得到最后的答案。

    时间复杂度：O(n)
        其中 n 为数组的长度。
        每个元素被翻转两次，所以时间复杂度为 O(2n) = O(n)。
    空间复杂度：O(1)
*/
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k = k % n;
        
        reverse(nums, 0, n-1);
        reverse(nums, 0, k-1);
        reverse(nums, k, n-1);
    }

    void reverse(vector<int>& nums, int l, int r) {
        while (l < r) {
            int temp = nums[l];
            nums[l] = nums[r];
            nums[r] = temp;
            l++, r--;
        }
    }
};
// 辅助函数：打印数组
void printArray(const vector<int>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]";
}

int main() {
    Solution solution;
    vector<vector<int>> nums_cases = {
        {1,2,3,4,5,6,7},
        {-1,-100,3,99}
    };
    vector<int> k_cases = { 3, 2 };

    for (int i = 0; i < nums_cases.size(); i++) {
        auto& nums = nums_cases[i];
        int k = k_cases[i];

        cout << "Input: nums = ";
        printArray(nums);
        cout << ", k = " << k << endl;
        solution.rotate(nums, k);
        cout << "Output: ";
        printArray(nums);
        cout << endl;
    }

    return 0;
}