189. Rotate Array
Last updated
Last updated
/**
* Time complexity : O(n×k). All the numbers are shifted by one step(O(n))
* k times(O(n)).
* Space complexity : O(1). No extra space is used.
*/
class Solution {
public void rotate(int[] nums, int k) {
// speed up the rotation
k %= nums.length;
int temp, previous;
for (int i = 0; i < k; i++) {
previous = nums[nums.length - 1];
for (int j = 0; j < nums.length; j++) {
temp = nums[j];
nums[j] = previous;
previous = temp;
}
}
}
}/**
* Time complexity : O(n). One pass is used to put the numbers in the new array.
* And another pass to copy the new array to the original one.
* Space complexity : O(n). Another array of the same size is used.
*/
class Solution {
public void rotate(int[] nums, int k) {
int[] a = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
a[(i + k) % nums.length] = nums[i];
}
for (int i = 0; i < nums.length; i++) {
nums[i] = a[i];
}
}
}/**
* Time complexity : O(n). Only one pass is used.
* Space complexity : O(1). Constant extra space is used.
*/
class Solution {
public void rotate(int[] nums, int k) {
k = k % nums.length;
int count = 0;
for (int start = 0; count < nums.length; start++) {
int current = start;
int prev = nums[start];
do {
int next = (current + k) % nums.length;
int temp = nums[next];
nums[next] = prev;
prev = temp;
current = next;
count++;
} while (start != current);
}
}
}/**
* Time complexity : O(n). n elements are reversed a total of three times.
* Space complexity : O(1). No extra space is used.
*/
class Solution {
public void rotate(int[] nums, int k) {
int n = nums.length;
k = k % n;
reverse(nums, 0, n-1);
reverse(nums, 0, k-1);
reverse(nums, k, n-1);
}
private void reverse(int[] nums, int left, int right) {
while(left < right) {
int tmp = nums[left];
nums[left] = nums[right];
nums[right] = tmp;
left++;
right--;
}
}
}