题目描述:
给定一个数组，将数组向右旋转k步，其中k为非负数
Example1
Input: [1,2,3,4,5,6,7] and k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
向右旋转一步: [7,1,2,3,4,5,6]
向右旋转两步: [6,7,1,2,3,4,5]
向右旋转三步: [5,6,7,1,2,3,4]
Example2
Input: [-1,-100,3,99] and k = 2
Output: [3,99,-1,-100]
Explanation:
向右旋转一步: [99,-1,-100,3]
向右旋转两步: [3,99,-1,-100]
C++输入格式
class Solution {
public:
void rotate(vector<int>& nums, int k) {
}
};
范例一
做一个额外的拷贝，然后旋转
class Solution{
public:
void rotate(vector<int>& nums, int k)
{
int n = nums.size();
if ((nums.size() == 0) || (k <= 0))
{
return;
}
// Make a copy of nums
vector<int> numsCopy(n);
for (int i = 0; i < n; i++)
{
numsCopy[i] = nums[i];
}
// Rotate the elements.
for (int i = 0; i < nums.size(); i++)
{// %取模运算符，整除后的余数
nums[(i + k)%nums.size()] = numsCopy[i];
}
}
};
main()
int main() {
vector<int> vec;
int i=0;
int a[10]={0,1,2,3,4,8};
int k =3;
for(i=0;i<6;i++)
{
vec.push_back(a[i]);
}
vector<int>::iterator pos;
//声明一个迭代器，来访问vector容器。作用:遍历或指向vector容器的元素
cout<<"输入数组:";
for(pos = vec.begin();pos!=vec.end();pos++)
{
cout<<*pos<<" ";
}
cout<<endl;
Solution sol;
sol.rotate(vec,k);
cout<<"输出数组:";
for(pos = vec.begin();pos!=vec.end();pos++)
{
cout<<*pos<<" ";
}
return 0;
}
测试样例
测试结果
首先对数组进行拷贝，然后根据k值决定需要旋转几次。
nums[3] = numsCopy[0]
nums[4] = numsCopy[1]
nums[5] = numsCopy[2]
nums[0] = numsCopy[3]
nums[1] = numsCopy[4]
nums[2] = numsCopy[5]
该方法的时间复杂度:O(n),空间复杂度:O(n)
范例二
class Solution
{
public:
void rotate(vector<int>& nums, int k)
{
int n = nums.size();
if ((n == 0) || (k <= 0))
{
return;
}
int cntRotated = 0;
int start = 0;
int curr = 0;
int numToBeRotated = nums[0];
int tmp = 0;
// Keep rotating the elements until we have rotated n
// different elements.
while (cntRotated < n)
{
do
{
tmp = nums[(curr + k)%n];
nums[(curr+k)%n] = numToBeRotated;
numToBeRotated = tmp;
curr = (curr + k)%n;
cntRotated++;
} while (curr != start);
cout<<cntRotated<<endl;
// Stop rotating the elements when we finish one cycle,
// i.e., we return to start.
// Move to next element to start a new cycle.
start++;
curr = start;
numToBeRotated = nums[curr];
}
}
};
测试样例
int a[10]={0,1,2,3,4,8};
int k =3;
输出每次do...while()循环后cntRotated值的变化情况
测试结果
变量cntRotated用来记录元素转换次数，每次两个元素换位置，该变量就会增加2。do....while()循环中记录每次旋转的元素旋转的方式和过程。如k=3,在do...while()循环中
tmp = nums[3] =3
nums[3] = numToBeRotated=nums[0]=0
numToBeRotated = tmp =3
curr = 3
cntRotated=1
//此时发现curr不等于start,继续循环。
tmp = nums[0] =0
nums[0] = numToBeRotated=3
numToBeRotated = tmp =0
curr = 0
cntRotated=2
//此时发现curr等于start,结束循环。继续往下执行，寻找下一个旋转元素。
