題目:
Rotate an array of n elements to the right by k steps.
For example, with n = 7 and k = 3, the array
[1,2,3,4,5,6,7]
is rotated to
[5,6,7,1,2,3,4]
.
Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
[show hint]
Hint:
Could you do it in-place with O(1) extra space?
Related problem: Reverse Words in a String II
思路:
本題應該有很多種不同解法,這裡提供其中一種比較簡單的解法。時間複雜度O(n),空間複雜度O(1)。
代碼:
class Solution {
public:
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);
}
void reverse(vector<int>& nums, int low, int high) {
while(low < high) {
int temp = nums[low];
nums[low] = nums[high];
nums[high] = temp;
++low, --high;
}
}
};