题目描述:
方法1:用一个新数组存最后 k 个数字,然后把最后 k 个数字之前的数字依次向后移动 k 位,最后把新数组中数组存回原数组头部
class Solution {
public:
void rotate(vector<int>& nums, int k) {
vector<int> temp(k);
for(int i=nums.size()-k; i<nums.size(); i++){
temp.push_back(nums[i]);
}
for(int i=nums.size()-k-1;i>=0;i--){
nums[i+k] = nums[i];
}
for(int i=0;i<k;i++){
nums[i] = temp[i];
}
}
};
出错,因为 push_back 是向数组末尾添加数字,应该把 vector<int> temp(k) 改为 vector<int> temp(0)
方法2:遍历原数组,将原数组下标为 i 的元素放至新数组下标为 (i+k) % n 的位置,最后将新数组拷贝至原数组
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
vector<int> temp(n);
for(int i=0;i<n;i++) temp[(i+k) % n] = nums[i];
nums = temp;
}
};
方法3:整体数组反转一次,然后前k个数字反转一次,最后剩下数字再反转一次
class Solution {
public:
void reverse(vector<int>& temp, int s, int e){
int n = (e+s)/2;
int m = 0;
for(int i=s;i<=n;i++){
m = temp[i];
temp[i] = temp[e];
temp[e] = m;
e = e-1;
}
}
void rotate(vector<int>& nums, int k) {
k = k % nums.size();
if(k == 0) return;
reverse(nums,0,nums.size()-1);
reverse(nums,0,k-1);
reverse(nums,k,nums.size()-1);
}
};
出错了三次:第一次,n写成(e-s)/2;第二次,没有加 if(k == 0) return,而 reverse(nums,0,-1)报错;第三次,if(k == 0) return写在了第一行,但是k为nums.size()时,k % nums.size()任然为0,更好的方法是,reverse 时,用 while 判断 s 和e 关系:
class Solution {
public:
void reverse(vector<int>& temp, int s, int e){
while(s < e){
swap(temp[s++],temp[e--]);
}
}
void rotate(vector<int>& nums, int k) {
k = k % nums.size();
reverse(nums,0,nums.size()-1);
reverse(nums,0,k-1);
reverse(nums,k,nums.size()-1);
}
};