题目描述
题解：
这道题的解法是多样的： 1. 直接模拟移动的过程，用两层循环来解决： 第一层循环表示移动k次，然后每次记录下最后一个值，第二层循环从倒数第二个数到第一个数依次往后移动一个位置，最后把记录下的值放到第一个位置。注意：这个方法使用c++过不了，使用java可以过。 2. 三次翻转法： 比如给定的样例：1、2、3、4、5、6、7 ，k=3，最后的结果应该为：5、6、7、1、2、3、4 首先全部翻转： 7、6、5、4、3、2、1 然后把0-k-1(2)的位置翻转：5、6、7、4、3、2、1 最后把k(3)-n-1(6)的位置翻转：5、6、7、1、2、3、4 注意：自己写的翻转函数一定要正确。 3. 利用一个tmp临时数组 提前将k%numsLen(因为大于numsLen实际上会做无效的翻转)，多开一个长度为numsLen的数组，然后O(n)遍历一次nums数组，tmp[(i+k)%numsLen] = nums[i]，最后将tmp数组的值赋给nums即可。
代码：
class Solution { public: void rotate(vector<int>& nums, int k) { /* 1. c++写就超时(java就不超时) int len = nums.size(); k %= len; for(int i = 1; i <= k; i++) { int lastElem = nums[len-1]; for(int j = len-2; j >= 0; j--) { nums[j+1] = nums[j]; } nums[0] = lastElem; }*/ /* 2. 三次翻转法 int len = nums.size(); k %= len; rotateANums(nums,0,len-1); rotateANums(nums,0,k-1); rotateANums(nums,k,len-1);*/ /* 3. 利用一个tmp数组 */ int numsLen = nums.size(); k %= numsLen; vector <int> tmp; for(int i = 0; i < numsLen; i++) { tmp.push_back(-1); } for(int i = 0; i < numsLen; i++) { tmp[(i+k)%numsLen] = nums[i]; } for(int i = 0; i < numsLen; i++) { nums[i]= tmp[i]; } } void rotateANums(vector<int>& nums,int l,int r) { // 给定一个nums数组，将l-r的元素翻转一遍 int len = r-l+1; int i,j; if(len % 2 == 0) { i = (l+r)/2; j = i+1; } else { int mid = (l+r)/2; i = mid-1; j = mid+1; } while(i >= l && j <= r) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; i--,j++; } } };