LeetCode 189: Rotate Array (Java)

NO IMAGE

題目: 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].


兩種解法:

第一種是原地swap,記錄下被擠掉的數再接著swap,需要一些時間舉栗子探索規律;

第二種是倒三次的方法,如果之前沒有準備過,面試中不太可能自己想出來。


解法一(12%):

假設陣列為[1,3,5,7,9], k = 2 :
先把1換到5的位置,把5拿著換到9的位置,把9拿著換到3的位置。。。最後7到了1的位置就換完了,貌似計劃通啊。
停止條件姑且假設為當置換的數回到陣列的首位。
不過換一個栗子上述方法就不通了,比如陣列為[1,3,5,7,9,11], k = 2, 換一輪發現結果是[9,3,1,7,5,11]。
這裡要從3開始重複一遍上述方法,所以要再套一個loop,i = 0, 停止條件為 最大公約數(陣列長度,k)。這樣所有的情況都能cover了。

public static void rotate(int[] nums, int k) {
if(nums == null || nums.length <= 1)
return;
k = k%nums.length;
int prev = 0;
int next = 0;
int maxComm = maxCommonDivisor(k,nums.length);
for(int i = 0; i < maxComm;i  ){
prev = nums[i];
int j = i k;
j %= nums.length;
while(j != i){
next = nums[j];
nums[j] = prev;
prev = next;
j =k;
j%=nums.length;
}
nums[j] = prev;
}
return;
}
private static int maxCommonDivisor(int m, int n){
while (m % n != 0) {
int temp = m % n;
m = n;
n = temp;
}
return n;
}


解法二(12%):

巧妙的reverse三次:
第一次reverse整個陣列;
第二次reverse子陣列(0,k-1);
第三次reverse子陣列(k,length-1)

reverse的函式都是一樣的,所以可以寫一個helper。

public static void rotate(int[] nums,int k) {
if(nums == null || nums.length <= 1)
return;
k %=nums.length;
if(k == 0)
return;
helper(nums,0,nums.length-1);
helper(nums,0,k-1);
helper(nums,k,nums.length-1);
}
public static void helper(int[] nums,int start,int end) {
for(int i = start; i <= (end start)/2;i  ) {
int temp = nums[end start-i];
nums[end start-i] = nums[i];
nums[i] = temp;
}
}

最後貼一下最快的code(98%):

public void rotate(int[] nums, int k) {
int n = nums.length;
k = k%n;
int[] temp = Arrays.copyOfRange(nums, 0, n-k);
System.arraycopy(nums, n-k, nums, 0, k);
System.arraycopy(temp, 0, nums, k, n-k);
}

Reference: 0ms 5-line java