1、題目描述
給定一個(gè)數(shù)組，將數(shù)組中的元素向右移動(dòng) k 個(gè)位置，其中 k 是非負(fù)數(shù)。
示例 1:
輸入: [1,2,3,4,5,6,7] 和 k = 3
輸出: [5,6,7,1,2,3,4]
解釋:
向右旋轉(zhuǎn) 1 步: [7,1,2,3,4,5,6]
向右旋轉(zhuǎn) 2 步: [6,7,1,2,3,4,5]
向右旋轉(zhuǎn) 3 步: [5,6,7,1,2,3,4]
示例 2:
輸入: [-1,-100,3,99] 和 k = 2
輸出: [3,99,-1,-100]
解釋:
向右旋轉(zhuǎn) 1 步: [99,-1,-100,3]
向右旋轉(zhuǎn) 2 步: [3,99,-1,-100]
說明:
盡可能想出更多的解決方案，至少有三種不同的方法可以解決這個(gè)問題。要求使用空間復(fù)雜度為 O(1)的原地算法。
2、解法
①：整體移動(dòng)法
以從下標(biāo)0開始長度為(size - k)的數(shù)組集合整體移動(dòng)k個(gè)單位，后面數(shù)字的依次往前移動(dòng),例如題目中舉出的第1個(gè)示例來說，
[1,2,3,4,5,6,7]移動(dòng)k = 3，也就是以第0個(gè)開始長度為（7 - 3 = 4）的數(shù)組集合([1,2,3,4])移動(dòng)3個(gè)長度單位
第一次移動(dòng)： [7,1,2,3,4,5,6]
第二次移動(dòng)： [6,7,1,2,3,4,5]
第三次移動(dòng)： [5,6,7,1,2,3,4]
public void rotate(int[] nums, int k) {
k = k % nums.length;
if (k == 0)return;
for(int j = 0;j <k;j++){
for (int i = j+(nums.length - 1 - k);i>=j;i--){
swapNum(nums,i,i+1);
}
}
}
public void swapNum(int[] num,int pre,int next){
if (next > num.length - 1||next <0) return;
num[pre] = num[pre]^num[next];
num[next] = num[pre]^num[next];
num[pre] = num[pre]^num[next];
}
這是正常的思路的解法，但是題目要求是O(1)的時(shí)間復(fù)雜度，而這個(gè)解法的時(shí)間復(fù)雜度卻是O(n^2)，因此不符合題目要求，這也有了下面的兩種解法。
②：翻轉(zhuǎn)法
這種解法需要畫一個(gè)圖來說明，請看下圖。
哈哈,在這里請忽略下字體不美觀的因素，還是來關(guān)注下主要算法核心，由此圖可以得出，可以分3步走，第一次是從0到(size - k - 1)的翻轉(zhuǎn)，第二次是（size - k）到size的翻轉(zhuǎn)，第三次是整體的翻轉(zhuǎn)。
第一次翻轉(zhuǎn)： [4,3,2,1,5,6,7]
第二次翻轉(zhuǎn)： [4,3,2,1,7,6,5]
第三次翻轉(zhuǎn)： [5,6,7,1,2,3,4]
代碼如下:
public void rotate(int[] nums, int k) {
k %= nums.length;
int i = nums.length-k;
reverse(nums, 0, i-1);
reverse(nums,i,nums.length-1);
reverse(nums,0,nums.length-1);
}
private void reverse(int[]nums, int start, int end){
while(start<end){
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
}
③：擴(kuò)展數(shù)組法（以空間換時(shí)間）
還是以[1,2,3,4,5,6,7]這個(gè)數(shù)組為例，可以再增加一個(gè)相同的數(shù)組成為[1,2,3,4,5,6,7,1,2,3,4,5,6,7]，當(dāng)移動(dòng)k = 3個(gè)時(shí)，可以從這個(gè)數(shù)組得知是從下標(biāo)(size - k)起長度為size的數(shù)組[5,6,7,1,2,3,4]
代碼如下:
public void rotate(int[] nums, int k) {
k = k % nums.length;
if (k == 0)return;
int[] numscopy = new int[nums.length * 2];
for (int i = 0; i < nums.length * 2; i++) {
numscopy[i] = nums[i%nums.length];
}
for (int i = nums.length - k;i<2 * nums.length - k;i++){
nums[i + k - nums.length] = numscopy[i];
}
}
經(jīng)測試，可行！
