博客

Rotate an array of

n

elements to the right by

k

steps.

For example, with

n

= 7 and

k

= 3, the array

[1,2,3,4,5,6,7]

is rotated to

[5,6,7,1,2,3,4]

.

Note:

Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem

class Solution {


public:

void rotate(vector<int>& nums, int k) {

//第一种方法，时间代价很大

//   k = k % nums.size();//k可能很大

//  int temp;

//  for(int i = 0; i < k; i++)//移位k次

//  {

//      temp = nums[nums.size()-1];

//      for(int j = nums.size()-1; j > 0 ; j–)

//      {

//         nums[j] = nums[j-1];

//     }

//     nums[0] = temp;

//  }

//第二种方法，拷贝内存方式[转载]

//int n = nums.size();

//if (k == 0) return;

//int *temp = new int[n];

//memcpy(temp, nums+(n-k-1), sizeof(int)*k);

//memcpy(temp+k, nums, sizeof(int)*(n-k));

//memcpy(nums, temp, sizeof(int)*n);

//delete[] temp;

//第三种方法，将后面k个数据保存在队列中

int n = nums.size();

if(n==0)return;

k=k%n;//当k大于n的时候，n次循环会回到初始位置，因此，可以省略若干次

if (k == 0)



return;

queue<int> s;//为了一步到位的展开移动，申请k个额外空间用于保存被移出去的元素，//需要额外空间O（k%n）

for(int i=0;i<k;++i)

{



s.push(nums[n-k+i]);

}

for(int j=n-k-1;j>=0;–j)



nums[j+k]=nums[j];//移动

for(int i=0;i<k;++i)

{



nums[i] = s.front();



s.pop();

}

}

};