題目
給定一個(gè)數(shù)組决侈，將數(shù)組中的元素向右移動(dòng) k 個(gè)位置深员，其中 k 是非負(fù)數(shù)。
說明:
- 盡可能想出更多的解決方案九巡，至少有三種不同的方法可以解決這個(gè)問題。
- 要求使用空間復(fù)雜度為 O(1) 的 原地 算法蹂季。
思路
借助額外空間
這個(gè)思路很簡單冕广，定位到需要旋轉(zhuǎn)的位置，重新構(gòu)造數(shù)組即可偿洁，但不符合題意撒汉，題目要求我們?cè)貙?shí)現(xiàn)。
旋轉(zhuǎn)元素
- 將整個(gè)數(shù)組反轉(zhuǎn)
- 將數(shù)組[0, k - 1]區(qū)間內(nèi)反轉(zhuǎn)
- 將[k, len-1]區(qū)間內(nèi)反轉(zhuǎn)
完成涕滋。
實(shí)現(xiàn)
借助額外空間
class Solution {
public void rotate(int[] nums, int k) {
int len = nums.length;
if (k % len == 0) return ;
k = k % len;
int[] temp = new int[len];
int count = 0;
for (int i = len - k; i < len; i++) {
temp[count++] = nums[i];
}
for (int i = 0; i < len - k; i++) {
temp[count++] = nums[i];
}
for (int i = 0; i < len; i++) {
nums[i] = temp[i];
}
}
}
旋轉(zhuǎn)元素
class Solution {
public void reverse(int[] nums, int l, int r) {
while (l < r) {
int temp = nums[l];
nums[l] = nums[r];
nums[r] = temp;
l++;
r--;
}
}
public void rotate(int[] nums, int k) {
int len = nums.length;
if (k % len == 0) return ;
k = k % len;
reverse(nums, 0, len - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, len - 1);
}
}
