Medium題。給一陣列及一非負整數,將陣列的每個元素向右移動整數個位置,右移的元素超過陣列長度則調到陣列頭部。
題目
Given an array, 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]
Constraints
1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105
Follow up:
- Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.
- Could you do it in-place with
O(1)
extra space?
先想到的解法
建立一個新陣列存放移動結果,用一個廽圈遍歷陣列,當索引小於位移數時,將陣列由後往前數的位移數後的元素從頭放到新陣列;當索引大於位移數時則放到新陣列位移數後的位置。時間複雜度O(n);空間複雜度O(n)。
nums=[1,2,3,4,5,6,7] k=3
rotatedNums=[0,0,0,0,0,0,0]
============================L1=============================
v(i=0) < k
rotatedNums=[5,0,0,0,0,0,0]
v
nums=[1,2,3,4,5,6,7]
============================L2=============================
v(i=1) < k
rotatedNums=[5,6,0,0,0,0,0]
v
nums=[1,2,3,4,5,6,7]
============================L3=============================
v(i=2) < k
rotatedNums=[5,6,7,0,0,0,0]
v
nums=[1,2,3,4,5,6,7]
============================L4=============================
v(i=3) >= k
rotatedNums=[5,6,7,1,0,0,0]
v
nums=[1,2,3,4,5,6,7]
============================L5=============================
v(i=4) >= k
rotatedNums=[5,6,7,1,2,0,0]
v
nums=[1,2,3,4,5,6,7]
============================L6=============================
v(i=5) >= k
rotatedNums=[5,6,7,1,2,3,0]
v
nums=[1,2,3,4,5,6,7]
============================L7=============================
v(i=6) >= k
rotatedNums=[5,6,7,1,2,3,4]
v
nums=[1,2,3,4,5,6,7]
Main.java
package com.abc.demo;
import java.util.Arrays;
public class Main {
public static void main(String[] arges) {
System.out.println(Arrays.toString(rotate(new int[]{1, 2, 3, 4, 5, 6, 7}, 3))); // [5, 6, 7, 1, 2, 3, 4]
System.out.println(Arrays.toString(rotate(new int[]{-1, -100, 3, 99}, 2))); // [3, 99, -1, -100]
System.out.println(Arrays.toString(rotate(new int[]{1, 2}, 5))); // [2, 1]
}
public static int[] rotate(int[] nums, int k) {
k = k % nums.length;
int[] rotatedNums = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
if (i < k) {
rotatedNums[i] = nums[nums.length - k + i];
} else {
rotatedNums[i] = nums[i - k];
}
}
System.arraycopy(rotatedNums, 0, nums, 0, rotatedNums.length);
return nums;
}
}
更加解
題目說至少有三種方法可解,且能只用O(1)空間複雜度在陣列內交換的解法。
參考討論區的O(1)解法如下,先將陣列翻轉,再把第一個元素到第k-1的元素翻轉,再把第k-1的元素到最後的元素翻轉。時間複雜度O(n);空間複雜度O(1)。我想這解法是觀察翻轉結果想出來的。
┌────k=3────┐
│ ▼
┌─┴─┬───┬───┬───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │
└───┴───┴───┴───┴───┴───┴───┘
step 1:reverse the whole array
┌───┬───┬───┬───┬───┬───┬───┐
│ 7 │ 6 │ 5 │ 4 │ 3 │ 2 │ 1 │
└───┴───┴───┴───┴───┴───┴───┘
step 2:reverse 0 to k-1 sub array
┌───┬───┬───┬───┬───┬───┬───┐
│ 5 │ 6 │ 7 │ 4 │ 3 │ 2 │ 1 │
└───┴───┴───┴───┴───┴───┴───┘
step 3:reverse k to end sub array
┌───┬───┬───┬───┬───┬───┬───┐
│ 5 │ 6 │ 7 │ 1 │ 2 │ 3 │ 4 │
└───┴───┴───┴───┴───┴───┴───┘
Main.java
package com.abc.demo;
import java.util.Arrays;
public class Main {
public static void main(String[] arges) {
System.out.println(Arrays.toString(rotate(new int[]{1, 2, 3, 4, 5, 6, 7}, 3))); // [5, 6, 7, 1, 2, 3, 4]
System.out.println(Arrays.toString(rotate(new int[]{-1, -100, 3, 99}, 2))); // [3, 99, -1, -100]
System.out.println(Arrays.toString(rotate(new int[]{1, 2}, 5))); // [2, 1]
}
public static int[] rotate(int[] nums, int k) {
k = k % nums.length;
reverse(nums, 0, nums.length - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, nums.length - 1);
return nums;
}
public static void reverse(int[] nums, int start, int end) {
int tmp;
while (start < end) {
tmp = nums[start];
nums[start] = nums[end];
nums[end] = tmp;
start++;
end--;
}
}
}
陣列反轉可參考Reverse String。
沒有留言:
張貼留言