轮转数组

// 给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。 // 示例 1: // 输入: nums = [1,2,3,4,5,6,7], k = 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] // 示例 2: // 输入：nums = [-1,-100,3,99], k = 2 // 输出：[3,99,-1,-100] // 解释: // 向右轮转 1 步: [99,-1,-100,3] // 向右轮转 2 步: [3,99,-1,-100] // 提示： // 1 <= nums.length <= 105 // -231 <= nums[i] <= 231 - 1 // 0 <= k <= 105 // 进阶： // 尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。 // 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？

这个问题本质上是反转矩阵，将如式（1）转变如式（2）所示， $$ \begin{equation} \begin{bmatrix} A & B \end{bmatrix} \end{equation} $$

$$ \begin{equation} \begin{bmatrix} B & A \end{bmatrix} \end{equation} $$

将矩阵进行反转操作，C++ 标准库中Algorithm的API template< class ForwardIt >ForwardIt rotate( ForwardIt first, ForwardIt middle, ForwardIt last );可以进行左旋操作，但是这个API在C++20 中才被支持，使用reverse会反转整个数组，这个会打乱数组A，B中元素的顺序，所以需要对数组A和B再次反转，恢复原始顺序。

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());
    }
    void leftrotate(vector<int>& nums,int k){
        int n=nums.size();
        k %=n;
        rotate(nums.begin(),nums.begin()+k,nums.end());
       	return;
    }
}

下面是别的语言的解法：

java

public class Solution {
    private  void reverse(int [] nums,int left,int right){
        while(left<right){  
            int tmp=nums[left];
            nums[left]=nums[right];
            nums[right]=tmp;
            left++;right--;
        }
    }
    public void rotate(int[] nums, int k) {
        int  size = nums.length;
        k = k%size;
        reverse(nums, 0, size-1);
        reverse(nums,0,k-1);
        reverse(nums, k, size-1);
    }
}

python

from typing import List

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        size=len(nums)
        k=k%size
        nums[:]=nums[-k:]+nums[:-k]

go

package main
func reverse(nums[] int, left,right int){
	for left<right{
		nums[left] ,nums[right] = nums[right],nums[left]
		left++
		right--
	}
}
func  rotate(nums []int, k int) {
	k=k%len(nums)
	reverse(nums,0,len(nums)-1)
	reverse(nums,0,k-1)
	reverse(nums,k,len(nums)-1)

}