題目描述:
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.
1.整個數組rotate
2.前k個數rotate
3.後面n-k個數rotate
時間復雜度O(n),空間復雜度O(1)
class Solution { public: void rotate(int nums[], int n, int k) { if(nums==NULL || n<=0 || k<=0) return ; k = k %n; for(int i =0;i<n/2;i++){ int temp = nums[i]; nums[i] = nums[n-i-1]; nums[n-i-1] = temp; } for(int i =0; i<k/2;i++){ int temp = nums[i]; nums[i] = nums[k-i-1]; nums[k-i-1] = temp; } int start = k; int tail = n; for(int i = start; i<start+(tail-start)/2; i++){ int temp = nums[i]; nums[i] = nums[tail-i+start-1]; nums[tail-i+start-1] = temp; } } };