今天和大家聊的问题叫做 旋转数组，我们先来看题面：https://leetcode-cn.com/problems/rotate-array/
Given an array, rotate the array to the right by k steps, where k is non-negative.
Follow up:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
Could you do it in-place with O(1) extra space?
题意
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。进阶：尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？
示例
示例 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]
解题:3种解法，见下图代码注释。
class Solution { public: //解法1：翻转，时间复杂度为O(n),空间复杂度为O(1) void rotate_1(vector<int>& nums, int k) { k%=nums.size(); reverse(nums.begin(),nums.end());//反转整个字符串 reverse(nums.begin(),nums.begin()+k);//前k个字符反转 reverse(nums.begin()+k,nums.end());//后面的字符反转 } //解法2：双重for,暴力数组旋转k次,时间复杂度为O(k*n),空间复杂度为O(1) void rotate_2(vector<int>& nums, int k) { k%=nums.size(); int n=nums.size(); for(int i=0;i<k;++i) { int temp=nums[n-1];//最后一个元素旋转到最前面 for(int j=n-1;j>0;--j)nums[j]=nums[j-1]; nums[0]=temp;//最后一个元素到底第一个元素的位置 } } //解法3：使用额外的数组，时间复杂度为O(n),空间复杂度为O(n) void rotate_3(vector<int>& nums, int k) { vector<int> record(nums.size()); //将数组nums中的元素放到右移k个单位后的record数组 for(int i=0;i<nums.size();++i) record[(i+k)%nums.size()]=nums[i]; nums.swap(record); } };
好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。
