题目
给定一个数组和一个数字n, 进行n次操作, 每次都将数组的最后一个数字放到最前面.
Input: [1,2,3,4,5,6,7], 3
Output: [5,6,7,1,2,3,4]
思路1
将后n个数字提到前面即可.也可以不利用额外数组, 但内存都一样.
void rotate(vector<int>& nums, int k) {
int n = (int)nums.size();
k = k % n;
vector<int> first = vector<int>(nums.begin()+(n-k), nums.end());
first.insert(first.end(), nums.begin(), nums.begin()+(n-k));
nums = first;
}
思路2
尽量利用更少的内存.
void rotate(vector<int>& nums, int k)
{
int n = (int)nums.size();
k = k % n;
if (k > n-k) {
// 前面移到后面
vector<int> temp = vector<int>(nums.begin(), nums.begin()+(n-k));
for (int i = 0; i < n;i++) {
if (i < k) {
nums[i] = nums[n-k+i];
} else {
nums[i] = temp[i-k];
}
}
} else {
// 后面移到前面
vector<int> temp = vector<int>(nums.begin()+(n-k), nums.end());
for (int i = 0; i < n;i++) {
if (n-1-i >= k) {
nums[n-1-i] = nums[n-1-i-k];
} else {
nums[n-1-i] = temp[n-1-i];
}
}
}
}
总结
对不同的情况分开分析, 尽量使用更少的内存.
网友评论