[LeetCode] 189. Rotate Array

轉自LeetCode

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].

<Solution>

這題和 Rotate List 是關聯題，資料結構變成 vector，難度有降低

解題想法一樣

• 因為 k 有可能很大，但 rotate 是會循環的，所以先將 k = k % nums.size()

• 接下來，就是把最後一個元素拿掉，並塞到前面，重覆這個動作 k 次

code 如下

	class Solution {
	public:
	void rotate(vector<int>& nums, int k) {
	if(nums.empty() || nums.size() == 1 || k == 0) {
	return;
	}
	//> only need to rotate k % nums.size() times
	k = k % nums.size();
	//> rotate elements
	while(k--) {
	nums.insert(nums.begin(), nums.back());
	nums.pop_back();
	}
	}
	};

view raw rotateArray_1.cpp hosted with ❤ by GitHub

這題還有另外一個想法(參考資料)

因為每次往右 shift，就是把最後面的元素移到最前面，其餘向右移動

所以其實可以先 reverse 整個 vector，把最後面的元素擺到最前面

1 2 3 4 5 6 7 ->  7 6 5 4 3 2 1

假設 k = 3，那麼代表最後一個元素 7 應該是會出現在位置 3 的地方

所以這邊將前 k 個元素再反轉，這樣前半部分就等同於往右 shift k 步

7 6 5 4 3 2 1 -> 5 6 7 4 3 2 1

最後，再把剩下的元素做反轉，就得到答案了

5 6 7 4 3 2 1 -> 5 6 7 1 2 3 4

code 如下

	class Solution {
	public:
	void rotate(vector<int>& nums, int k) {
	if(nums.empty() || nums.size() == 1 || k == 0) {
	return;
	}
	k = k % nums.size();
	reverse(nums.begin(), nums.end());
	reverse(nums.begin(), nums.begin() + k);
	reverse(nums.begin() + k, nums.end());
	}
	};

view raw rotateArray_2.cpp hosted with ❤ by GitHub