完整解析題目：數(shù)組移位的實現(xiàn)，以及逐步優(yōu)化

要求：已知一個一維數(shù)組 arr ，現(xiàn)在要求將它向左旋轉(zhuǎn)n個位置。

方法一：

假設(shè)允許開辟一個臨時空間，那么問題就變得簡單了，可以開辟一個跟arr長度相同的空間，然后隔n個位置不斷添加元素即可，

思路比較簡單，下面是代碼實現(xiàn)：

void RotateLeft1(vector<int> &arr, const int step)
{
	vector<int> ret;
	int sz = arr.size();
	ret.resize(sz);
	for (int i = 0; i < arr.size(); ++i)
	{
		ret[ (sz + i - step) % sz ] = arr[i];
	}
	arr = ret;
}

方法二：

如果不允許開辟輔助空間，那就只能對現(xiàn)有的一維數(shù)組進(jìn)行操作了，可以實現(xiàn)一個每次左移一位的函數(shù)RotateLStep()：

///// 之前的第一種方法由于要考慮new開辟的輔助空間的回收問題，數(shù)組使用了STL中的vector。而此處開始數(shù)組全部用傳統(tǒng)的數(shù)組
void RotateLStep(int *arr, int sz)   //向左移動一位
{
	int first = arr[0];
	for (int i = 0; i < sz - 1; ++i)
	{
		arr[i] = arr[i + 1];
	}
	arr[sz - 1] = first;
}

void RotateLeft2(int *arr, int sz, int step)
{
	while (step--)
	{
		RotateLStep(arr, sz);
	}
}

但是顯而易見，這種方法的效率太低了，RotateLStep()的時間復(fù)雜度為 O(N * N)

/*

優(yōu)化：

數(shù)組長度為sz，那么向左移動n位就等價于向右移動(sz - n)位，那么可以比較并判斷出需要移動步數(shù)較少的方向，以進(jìn)一步提高效率

*/

方法三：

這個方法，在《編程珠璣》里，被叫做“雜技算法”，套路還是比較深的

具體的思路是：

先保存arr[0],然后把a(bǔ)rr[0] = arr[step % sz]

然后 arr[step % sz] = arr[2*step % sz]

然后 arr[2step % sz] = arr[3*step % sz]

......

循環(huán)結(jié)束的條件為 運(yùn)行 sz - 1 次

最后一次，讓當(dāng)前的目標(biāo)索引的值 = 最開始保存的 arr[0]  的值

即可。

上代碼：

///////////////////第三種方法
void RotateLeft3(int *arr, int sz, int step)
{
	if (step == sz)  //避免后面可能出現(xiàn)的死循環(huán)
	{
		return;
	}
	int tmp = arr[0];
	int dst_index = 0;
	int src_index = step;
	int count = sz;
	while(--count)  //移動了 sz 次（加上最底下那一次），或者說，時間復(fù)雜度是 O（N）
	{
		arr[ dst_index % sz ] = arr[ src_index % sz ];
		dst_index += step;
		src_index += step;
	}
	arr[dst_index % sz] = tmp;
}

可以看出，程序執(zhí)行的過程中，對數(shù)組內(nèi)的元素移動，或者說賦值了 sz 次,

所以這個方法的時間復(fù)雜度是 O(N)，并且不需要開辟輔助空間，是一種比較高效的算法了

方法四：

從向量的角度思考這個問題： （題設(shè)： 數(shù)組 0 1 2 3 4 5 6 7， 左移3位）

可以把這個數(shù)組 分成3部分： a 、b1 、b2

接下來，做以下幾件事：

1：交換 a 和 b2 ，得到 b2 b1 a向量（這一步執(zhí)行完，a 已經(jīng) 放在了 最終的位置）

2: 交換b1 b2 的位置,得到 b1 b2 a 向量，也是最終我們需要的數(shù)組

以上為推論，將這些交換步驟中相似的部分總結(jié)歸納，問題就變得很簡單，只需要3次交換即可，如下圖：

提煉出的代碼比較簡單，具體如下：

/////////////////////第四種方法：
/////////////////////第四種方法：
void ReverseArr(int *arr, int begin, int end)	//數(shù)組 begin 到 end 之間的部分 逆序
{
	int *a = arr + begin;
	int sz = end - begin + 1;
	for (int i = 0; i < sz / 2; ++i) //注意！ 這個方法要比下面注釋的那種方法效率高一倍！
	{
		int tmp = a[i];
		a[i] = a[sz - 1 - i];
		a[sz - 1 - i] = tmp;
	}
	/*while (begin < end)
	{
		int tmp = arr[begin];
		arr[begin++] = arr[end];
		arr[end--] = tmp;
	}*/
}


void RotateLeft4(int *arr, int sz, int step)
{
	ReverseArr(arr, 0, step - 1);
	ReverseArr(arr, step, sz - 1);
	ReverseArr(arr, 0, sz - 1);
}

可以看出 每次逆序的時間復(fù)雜度分別為 O(step)  O(N - step) O(N / 2)

總共的時間復(fù)雜度是一個略小于N的值，也是這個問題的的最優(yōu)實現(xiàn)方式

（完）