189 轮转数组
k没有说一定比数组长度小,所以需要做取余处理k = k % nums.size();
做法一
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
vector<int> newArr(n);
for(int i = 0; i < n; i++){
int idx = (i + k) % n;
newArr[idx] = nums[i];
}
nums.assign(newArr.begin(), newArr.end());
}
};
时间复杂度:\(O(n)\)
空间复杂度:\(O(n)\)
做法二
我也想不出怎么解释这个思路的来源,只能死记了
class Solution {
public:
void rotate(vector<int>& nums, int k) {
k = k % nums.size();
reverse(nums.begin(), nums.end());
reverse(nums.begin(), nums.begin() + k);
reverse(nums.begin() + k, nums.end());
}
};
时间复杂度:\(O(n)\)
空间复杂度:\(O(1)\)