Given an integer array nums
, rotate the array to the right by k
steps, where k
is non-negative.
Example 1:
Input: nums = [1,2,3,4,5,6,7], k = 3 Output: [5,6,7,1,2,3,4] Explanation: rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate 2 steps to the right: [6,7,1,2,3,4,5] rotate 3 steps to the right: [5,6,7,1,2,3,4]
Example 2:
Input: nums = [-1,-100,3,99], k = 2 Output: [3,99,-1,-100] Explanation: rotate 1 steps to the right: [99,-1,-100,3] rotate 2 steps to the right: [3,99,-1,-100]
Approach 1
class Solution {
public:
// used extra space
int n = nums.size();
vector<int> temp;
for(int i=0; i<n-k; i++) {
temp.push_back(nums[i]);
}
int index=0;
for(int i=n-k; i<n; i++) {
nums[index++] = nums[i];
}
for(int i=0; i<temp.size(); i++) {
nums[index++] = temp[i];
}
};
Approach 2
class Solution {
public:
// rotate : array 0 to n-k
// rotate : array n-k to n
//rotate : array 0 to n
k = k % nums.size();
reverse(nums.begin(), nums.begin()+(nums.size()-k));
reverse(nums.begin()+(nums.size()-k), nums.end());
reverse(nums.begin(), nums.end());
};
Approach 3
class Solution {
public:
// using pre-defined vector functon(reverse)
int n = nums.size();
k = k % n;
reverse(nums.begin(), nums.end());
reverse(nums.begin(), nums.begin()+k);
reverse(nums.begin()+k, nums.end());
};
Approach 4
class Solution {
public:
void reverse(vector<int>& nums, int left, int right) {
int i=left;
int j=right;
while(i < j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
i++;
j--;
}
}
void rotate(vector<int>& nums, int k) {
k=k%nums.size();
reverse(nums, 0, nums.size()-k-1);
reverse(nums, nums.size()-k, nums.size()-1);
reverse(nums, 0, nums.size()-1);
}
};