面試經典 150 題 ---- 輪轉數組
- 輪轉數組
- 方法一：使用額外的數組
- 方法二：數組翻轉
輪轉數組
方法一：使用額外的數組
我們可以使用額外的數組來將每個元素放至正確的位置。用 n 表示數組的長度，我們遍歷原數組，將原數組下標為 i 的元素放至新數組下標為 (i+k)?mod?n 的位置，最后將新數組拷貝至原數組即可。
class Solution {public void rotate(int[] nums, int k) {int len = nums.length;int[] newArr = Arrays.copyOf(nums, len);for (int i = 0; i < len; i ++ ) {nums[(i + k) % len] = newArr[i];}}
}
時間復雜度： O(n)
空間復雜度： O(n)
java 中拷貝數組的方法：
- System.arraycopy() 方法:
System.arraycopy(源數組, 源數組起始位置, 目標數組, 目標數組起始位置, 拷貝長度);
int[] sourceArray = {1, 2, 3, 4, 5};
int[] destinationArray = new int[5];
System.arraycopy(sourceArray, 0, destinationArray, 0, sourceArray.length);
- Arrays.copyOf() 方法:
int[] newArray = Arrays.copyOf(源數組, 新數組長度);
int[] sourceArray = {1, 2, 3, 4, 5};
int[] newArray = Arrays.copyOf(sourceArray, sourceArray.length);
- Arrays.copyOfRange() 方法:
int[] newArray = Arrays.copyOfRange(源數組, 起始位置, 結束位置);
int[] sourceArray = {1, 2, 3, 4, 5};
int[] newArray = Arrays.copyOfRange(sourceArray, 0, sourceArray.length);
- 使用clone() 方法:
int[] newArray = sourceArray.clone();
int[] sourceArray = {1, 2, 3, 4, 5};
int[] newArray = sourceArray.clone();
方法二：數組翻轉
我們將數組向右移動 k 個位置，那么數組尾部的 k % n 個元素就會移動到數組的頭部，同樣數組中其它元素就會向后移動 k % n 個位置。
我可以將整個數組進行一次翻轉，這樣尾部的 k % n 個數組就會移動到頭部，然后再分別翻轉 [0, k % n - 1] 部分的數組和 [k % n, n - 1] 部分的數組就可以得到答案。
class Solution {public void rotate(int[] nums, int k) {int len = nums.length;reverse(nums, 0, len - 1);reverse(nums, 0, k % len - 1);reverse(nums, k % len, len - 1);}public void reverse(int[] nums, int start, int end) {while (start < end) {int temp = nums[start];nums[start] = nums[end];nums[end] = temp;start += 1;end -= 1;}}
}
時間復雜度： O(n)
其中 n 為數組的長度。每個元素被翻轉兩次，一共 n 個元素，因此總時間復雜度為 O(2n)=O(n)
空間復雜度： O(1)
)
