用额外数组的话,时间和空间复杂度都是O(n)
不用二维数组直接循环移动k×n次暴力会超时,时间复杂度达到了O(kn)
考虑轮转的结果,向右移动k个位置的结果相对于整体翻转一次,然后0到k-1翻转一次,k到n-翻转一次的结果,向左移动的话则是k=n-k即可,让k=k%n去掉无效移动,这样每个元素被移动2次,时间复杂度为O(n)
class Solution {
public:
void rotate(vector<int> &nums, int k) {
auto reverse = [](vector<int> &nums, int begin, int end) -> void {
while (begin < end) {
swap(nums[begin++], nums[end--]);
}
};
k = k % nums.size();
reverse(nums, 0, nums.size() - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, nums.size() - 1);
}
};