Leetcode No.189(Rotate Array) 心得
題目:
Rotate an array of n elements to the right by k steps.
For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].
Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
Hint:
Could you do it in-place with O(1) extra space?
想法:
第一個想法當然就是用另外一個 array 記錄,但是提示要求用 O(1) space。
後來想到 “Cyclic Replacements”。
ex: 假設 n = 7, k =2: 0->2->4->6->1->3->5
這樣整個 array 就取代完成。
後來找幾個例子發現有些會繞回原點
ex: 假設 n = 6 , k =2: 0->2->4->0
那這時候就需要再由下一個數字開始搜尋 1->3->5->1
終止條件就是取代的個數等於 n。
我的答案:(我好像沒有考慮empty array 的 case,可能也沒有這個 test case)
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int count = 0;
int size = nums.size();
int begin = 0;
int index = begin + k % size;
int replace1 = nums[begin];
int replace2;
while (count < size) {
replace2 = nums[index];
nums[index] = replace1;
replace1 = replace2;
if (index == begin) {
begin++;
index = begin;
replace1 = nums[begin];
}
count++;
index = (index + k) % size;
}
}
};
網路上解答:
我之前只想到用 extra array,網路上有不使用 extra array 的暴力法:
array shift 一個數字! 如果 k = 5 的話,就要做 5 次的 “array shift 一個數字”。
另外個解法就和我一樣,只是他是 for loop + while,while 找這個系列的取代,for loop 就是加一然後交給 while 去找這個系列取代,while 終止條件就是回到原點。
public class Solution {
public void rotate(int[] nums, int k) {
k = k % nums.length;
int count = 0;
for (int start = 0; count < nums.length; start++) {
int current = start;
int prev = nums[start];
do {
int next = (current + k) % nums.length;
int temp = nums[next];
nums[next] = prev;
prev = temp;
current = next;
count++;
} while (start != current);
}
}
}