[C++]Rotate Array 旋轉數組

leetcode 原題連結：https://leetcode.com/problems/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.

簡要翻譯：題目要求就是将一個數組右移k步，例如  長度為7 的數組[1, 2, 3, 4, 5, 6, 7] 右移3 步 就是講最後三個數移動到前面來 即[5, 6, 7, 1, 2, 3, 4]；

提示：盡力提出多種方法解決這個問題，至少有三種方法可以解決。

簡要分析：

1、根據題目的意思，最容易想到的做法就是每次都将數組的最後一位移動到數組的第一位，這樣每次的移動次數為n，一共要循環k次，是以時間複雜度為O(n*k)。

2、根據July大神的思路，我們可以采用三次移動的方式來完成，其中用到的公式是(X'Y')' = YX。即首先将0~size-k-1進行首尾交換操作，然後将size-k~size-1進行首尾交換操作，最後将整個數組進行首尾交換操作。時間複雜度為O(2n) = O(n)

實作代碼

#include <iostream>
#include <vector>

using namespace std;

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

	void rotate(vector<int>& nums, int start, int end)
	{
		int temp = 0;
		while (start < end)
		{
			temp = nums[start];
			nums[start] = nums[end];
			nums[end] = temp;
			start++;
			end--;
		}
		return;
	}

	void display(vector<int> nums)
	{
		for (vector<int>::iterator p = nums.begin(); p != nums.end(); p++)
		{
			cout << *p << " ";
		}
		cout << endl;
	}
};

int main()
{
	int nums[] = { 1, 2, 3, 4, 5, 6, 7 };
	vector<int> intVector(nums, nums + 7);
	Solution st;
	st.rotate(intVector, -2);
	st.display(intVector);
	return 0;
}