轮转数组

题目要求

给定一个整数数组 nums，需要将数组中的所有元素向右移动 k 个位置，这里的 k 是一个非负整数。轮转操作是指将数组末尾的元素移动到数组的开头。

解题思路

解决这个问题的关键是找到一个高效的方法来进行数组元素的移动，因为直接按照定义进行移动会涉及到多次的数组遍历，这在 k 很大或数组很长时会非常低效。以下是解决这个问题的几个步骤：

处理 k 的值：由于数组的长度是固定的，所以当 k 大于数组长度 n 时，移动 k 次和移动 k % n 次的效果是相同的。因此，首先计算 k = k % n 来简化问题。
数组翻转：可以通过三次翻转数组的方式来达到向右轮转的效果。
- 首先，翻转整个数组，这会将原本在数组末尾的元素移动到数组的开头。
- 然后，翻转数组的前 k 个元素。
- 最后，翻转数组剩余的 n - k 个元素。

这个方法的优点是只需要线性时间复杂度 O(n)，并且可以在不需要额外空间的情况下（除了少量的临时变量）完成数组的轮转操作。

Golang 版本

package main

import (
	"fmt"
)

func rotate(nums []int, k int) {
	n := len(nums)
	k = k % n
	reverse(nums, 0, n-1)
	reverse(nums, 0, k-1)
	reverse(nums, k, n-1)
}

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

func main() {
	nums := []int{1, 2, 3, 4, 5, 6, 7}
	k := 3
	rotate(nums, k)
	fmt.Println(nums) // Output should be [5,6,7,1,2,3,4]
}

这段代码定义了一个 rotate 函数，它接受一个整数数组 nums 和一个整数 k，并将 nums 中的元素向右轮转 k 个位置。reverse 函数用于翻转数组中从 start 到 end 位置的元素。main 函数提供了一个示例用法。

C++版本

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

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

int main() {
    std::vector<int> nums = {1, 2, 3, 4, 5, 6, 7};
    int k = 3;
    rotate(nums, k);
    for (int num : nums) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

这段代码定义了一个 rotate 函数，它接受一个整数向量 nums 和一个整数 k，并将 nums 中的元素向右轮转 k 个位置。这里使用了 C++ STL 中的 std::reverse 函数来翻转向量的部分区间。main 函数提供了一个示例用法，并打印出轮转后的数组。

Python 版本

def rotate(nums, k):
    n = len(nums)
    k = k % n
    nums[:] = nums[-k:] + nums[:-k]

if __name__ == "__main__":
    nums = [1, 2, 3, 4, 5, 6, 7]
    k = 3
    rotate(nums, k)
    print(nums)  # Output should be [5, 6, 7, 1, 2, 3, 4]

这段代码定义了一个 rotate 函数，它接受一个整数列表 nums 和一个整数 k，并将 nums 中的元素向右轮转 k 个位置。这里使用了 Python 列表切片的特性来简化数组的旋转操作。if __name__ == "__main__": 部分提供了一个示例用法，并打印出轮转后的列表。

Java 版本

public class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        reverse(nums, 0, n - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
    }

    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1, 2, 3, 4, 5, 6, 7};
        int k = 3;
        solution.rotate(nums, k);
        for (int num : nums) {
            System.out.print(num + " ");
        }
    }
}

这段代码定义了一个 Solution 类，其中包含了一个 rotate 方法用于执行数组的旋转操作，以及一个辅助的 reverse 方法用于翻转数组中指定区间的元素。main 方法提供了一个示例用法，并打印出旋转后的数组。

Rust 版本

fn rotate(nums: &mut Vec<i32>, k: i32) {
    let n = nums.len() as i32;
    let k = k % n;
    nums.reverse();
    nums[..k as usize].reverse();
    nums[k as usize..].reverse();
}

fn main() {
    let mut nums = vec![1, 2, 3, 4, 5, 6, 7];
    let k = 3;
    rotate(&mut nums, k);
    println!("{:?}", nums); // Output should be [5, 6, 7, 1, 2, 3, 4]
}

这段代码定义了一个 rotate 函数，它接受一个可变引用的整数向量 nums 和一个整数 k，并将 nums 中的元素向右轮转 k 个位置。Rust 的切片和方法调用用于翻转向量的部分区间。main 函数提供了一个示例用法，并打印出轮转后的向量。

总结

上述解法中，无论是在 Golang、C++、Python 还是 Java 和 Rust 语言中，核心算法思想都是相同的，即通过三次数组翻转来实现数组的轮转操作。具体步骤如下：

首先，将整个数组翻转，这样数组末尾的元素就被移动到了数组的开头。
其次，翻转数组中前 k 个元素，其中 k 是经过模数组长度后的轮转次数。
最后，翻转剩余的元素，即从第 k+1 个元素到数组的末尾。

这种方法的时间复杂度是 O(n)，空间复杂度是 O(1)，因为它只需要对数组进行几次遍历，并且不需要额外的存储空间（除了几个用于交换的临时变量）。

不同编程语言之间的主要区别在于语法和数组操作的具体实现。例如：

在 C++ 中，使用了 STL 中的 std::reverse 函数来翻转数组的一部分。
在 Python 中，利用了列表切片的特性来一步完成轮转。
在 Java 中，通过手动交换数组元素来实现翻转。
在 Rust 中，使用了切片和 reverse 方法来翻转向量的部分区间。
在 Golang 中，通过索引和循环来手动翻转切片的元素。

尽管实现的细节不同，但所有这些解法都遵循了相同的算法逻辑。

hot-100