Leetcode No.189(Rotate Array) 心得

ChingYuanYang
Aug 28, 2017 · 2 min read

題目:
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);
}
}
}
)
Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade