Rotate Array (E)
題目
Given an array, rotate the array to the right by k steps, where k is non-negative.
Example 1:
Input: [1,2,3,4,5,6,7] and 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: [-1,-100,3,99] and 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]
Note:
- Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
- Could you do it in-place with O(1) extra space?
題意
將給定數列的指定后半部分與前半部分換位，得到新陣列，
思路
最經典的\(O(1)\)空間方法是翻轉法：先將左子陣列翻轉，再將右子陣列翻轉，最后將整個陣列翻轉，得到的就是目標陣列，
比較直接的是按照步驟一個一個移動元素，或者使用額外陣列先將右子陣列保存下來再處理，
官方解答還提供了一種回圈替換法：以一個元素為起點，直接將該元素放在它應在的位置上，并將該位置上原本的元素繼續按上述操作放在下一個位置上，直到回到起點完成一次回圈，接著更換起點重復操作即可，當這種放置進行了n次后，所有元素都已經在它應在的位置上，該方法是對暴力法的一種優化，
代碼實作
Java
翻轉法
class Solution {
public void rotate(int[] nums, int k) {
k = k % nums.length;
reverse(nums, 0, nums.length - 1 - k);
reverse(nums, nums.length - k, nums.length - 1);
reverse(nums, 0, nums.length - 1);
}
private void reverse(int[] nums, int left, int right) {
while (left < right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
}
}
暴力法
class Solution {
public void rotate(int[] nums, int k) {
for (int i = 0; i < k; i++) {
int pre = nums[nums.length - 1];
for (int j = 0; j < nums.length; j++) {
int temp = nums[j];
nums[j] = pre;
pre = temp;
}
}
}
}
額外陣列
class Solution {
public void rotate(int[] nums, int k) {
k = k % nums.length;
int[] temp = Arrays.copyOfRange(nums, nums.length - k, nums.length);
for (int i = nums.length - 1; i >= k; i--) {
nums[i] = nums[i - k];
}
for (int i = 0; i < k; i++) {
nums[i] = temp[i];
}
}
}
回圈替換
class Solution {
public void rotate(int[] nums, int k) {
k = k % nums.length;
int count = 0;
// 當count==nums.length時，說明所有元素都已經在它應在的位置上
for (int i = 0; count < nums.length; i++) {
int j = i;
int pre = nums[j];
do {
int next = (j + k) % nums.length;
int temp = nums[next];
nums[next] = pre;
pre = temp;
j = next;
count++;
} while (j != i); // 回到起點，說明一次回圈完成
}
}
}
JavaScript
/**
* @param {number[]} nums
* @param {number} k
* @return {void} Do not return anything, modify nums in-place instead.
*/
var rotate = function (nums, k) {
k %= nums.length
nums
.slice(0, nums.length - k)
.reverse()
.concat(nums.slice(nums.length - k).reverse())
.reverse()
.forEach((v, i) => (nums[i] = v))
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/172582.html
標籤：其他
上一篇：dynamics 365 The given key was not present in the dictionary
下一篇：試用 Azure Sql 資料庫