leetcode189：旋转数组

题目链接

leetcode

题目描述

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

C++ 代码

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

void printArray(const vector<int>& nums) {
    cout << "[";
    for (const int& num : nums) {
        cout << num << ",";
    }
    cout << "]" << endl;
}

/*
    使用额外的数组，将每个元素放至正确的位置。
    遍历原数组，将原数组下标为 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 次后，尾部 k % n 个元素移动至数组头部，其余元素向后移动 k % n 个位置。
    思路：
        先将所有元素翻转，尾部的 k % n 个元素就被移至数组头部，
        然后再翻转 [0, k % n − 1] 元素和 [k % n, n − 1] 元素，得到最后的答案。

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

    void reverseArray(vector<int>& nums, int l, int r) {
        while (l < r) {
            int temp = nums[l];
            nums[l] = nums[r];
            nums[r] = temp;
            l ++, r --;
        }
    }
};

/*
    环状替换
    
    数学推导的理解有一定困难，也可以使用另外一种方式完成。
    单独的变量 count 跟踪当前已经访问的元素数量，当 count = n 时，结束遍历过程。

    时间复杂度：O(n)
        其中 n 为数组的长度。数组中的每个元素只会被遍历一次。
    空间复杂度：O(1)
        常数空间存放若干变量。
*/
class Solution_2 {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k = k % n;
        int count = gcd(k, n);
        for (int start = 0; start < count; start ++) {
            int cur = start;
            int prev = nums[start];
            do {
                int next = (cur + k) % n;
                swap(nums[next], prev);
                cur = next;
            } while (start != cur);
        }
    }

    int gcd(int a, int b) {
        return b ? gcd(b, a % b) : a;
    }
};

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

    for (int i = 0; i < nums.size(); i ++) {
        vector<int> temp = nums[i];
        cout << "Input: ";
        printArray(temp);
        solution.rotate(temp, k_nums[i]);
        cout << "Output: ";
        printArray(temp);
    }

    return 0;
}

Golang 代码

package main

import (
	"fmt"
)

/*
   基本思路：
       1.k 对数组长度取模，得到实际需要移动的位置 k_mod。
       2.通过三次反转操作实现数组的轮转：
           反转整个数组。
           反转前 k_mod 个元素。
           反转后 n - k_mod 个元素。

   时间复杂度：O(n)
       其中 n 是数组的长度，三次反转操作的时间复杂度均为 O(n)。
   空间复杂度：O(1)
       只使用了固定的几个变量。
*/
func rotate(nums []int, k int)  {
    n := len(nums)
    k = k % n

    // 反转整个数组
    reverse(nums, 0, n - 1)
    // 反转数组中前 k 个元素
    reverse(nums, 0, k - 1)
    // 反转数组中后 k 个元素
    reverse(nums, k, n - 1)
}

func reverse(nums []int, start, end int) {
    for start < end {
        nums[start], nums[end] = nums[end], nums[start]
        start ++
        end --
    }
}

/*
    基本思路：
        1.k 对数组长度取模，得到实际需要移动的位置 k_mod。
        2.初始化一个计数器 count 为 0。
        3.从起始位置 0 开始，进行以下环状替换操作，直到计数器 count 等于数组长度 n。
        若回到了起始位置，则结束本次环状替换。

    时间复杂度：O(n)
        其中 n 是数组的长度，每个元素只会被访问和移动一次。
    空间复杂度：O(1)
        只使用了固定的几个变量。
*/
func rotate_1(nums []int, k int)  {
    n := len(nums)
    k = k % n

    for start, count := 0, gcd(k, n); start < count; start ++ {
        prev, cur := nums[start], start

        // 进行环状替换，直到回到起始位置
        for ok := true; ok; ok = cur != start {
            next := (cur + k) % n
            nums[next], prev = prev, nums[next]
            cur = next
        }
    }
}

func gcd(a, b int) int {
    for b != 0 {
        a, b = b, a % b
    }
    return a
}

func main() {
    // 测试用例
	testCases := []struct {
        nums     []int
		k        int
		expected []int
	}{
		{[]int{1,2,3,4,5,6,7}, 3, []int{5,6,7,1,2,3,4}},
		{[]int{-1,-100,3,99}, 2, []int{3,99,-1,-100}},
	}

    for i, tc := range testCases {
		fmt.Printf("Test Case %d: Input: nums = %v, k = %d\n", i+1, tc.nums, tc.k)
		rotate(tc.nums, tc.k)
        resultStr := fmt.Sprintf("%v", tc.nums)
        expectedStr := fmt.Sprintf("%v", tc.expected)

		if resultStr == expectedStr {
			fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, resultStr)
		} else {
			fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, resultStr, expectedStr)
		}
	}
}