下面请看一道算法题：
设将n (n>1) 个整数存放到一维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法，将R中保存的序列循环左移p (0<p<n) 个位置，即将R中的数据序列由(x0， x1，……，xn-1)变换为(xp，xp+1，……，xn-1，x0，x1，……，xp-1)。
在没学算法之前，我们习惯了使用简单的求解方法：借助一个临时数组B首先将数组R前p个元素保存，然后将R中的所有元素往左移动p个位置，最后将数组B的元素还原到数组R的后面p个位置。具体的代码实现为：
void leftMoveArray(int arr[], int len, int p) {
if (p <= 0 || p > len)
{
return;
}
//开辟临时数组空间
int* B = new int[p];
//将arr数组的前p个元素保存到数组B中
for (int i = 0; i < p;i ++) {
B[i] = arr[i];
}
//将数组arr的元素向左移动p个位置
for (int i = 0; i < len - p; i++)
{
arr[i] = arr[i+p];
}
//将数组B的元素还原到数组R的后面p个位置
for (int i = 0; i < p;i++) {
arr[len -p + i ] = B[i];
}
//释放资源
delete[] B;
cout << "数组向左移动" << p << "位的结果是：";
for (int i = 0; i < len; i++)
{
cout << arr[i] << " ";
}
cout << endl;
}
下面开始测试：
int main() {
int arr0[] = { 1,5,3,24,8,7,34,23,4 };
cout << "数组移动前：";
for (int i = 0; i < 9; i++)
{
cout << arr0[i] << " ";
}
leftMoveArray(arr0, 9, 5);
int arr1[] = {7,5,39,24,2,4,5};
cout << "数组移动前：";
for (int i = 0; i < 7; i++)
{
cout << arr1[i] << " ";
}
leftMoveArray(arr1, 7, 5);
int arr2[] = { 1,5,3,24,8,7,5,64,34,23,4 };
cout << "数组移动前：";
for (int i = 0; i < 11; i++)
{
cout << arr2[i] << " ";
}
leftMoveArray(arr2, 11, 5);
system("pause");
return 0;
}
该算法比较简单易懂，其时间复杂度为：O（n）,空间复杂度为：O（p），但题给的条件是： 试设计一个在时间和空间两方面都尽可能高效的算法，这道题还有没有更优的算法呢？
下面我们再来分析：该题目的等价命题：将数组左移p个元素,我们可以看成是将数组AB(A表示数组前p个元素，B表示数组的后n-p个元素)，逆置成BA，
在《线性代数》中，根据矩阵的运算，我们可以知道：
由此，我们可以根据矩阵的逆置运算来入手：
将数组左移p个元素,我们可以看承是将数组AB(A表示数组前p个元素，B表示数组的后n-p个元素)，逆置成BA，根据矩阵的运算，可以等价为：BA=(A^-1 * B ^ -1)^-1 ,那么将数组左移p个元素就可以看成是：先将数组A和B分别逆置得到：A^-1 * B ^ -1，然后将A^-1 * B ^ -1整体逆置得到BA。
步骤为：
(1)首先将数组看成两部分：AB，A表示数组前p个元素，B表示数组的后n-p个元素
(2)将数组A逆置（得到 A^ -1）
(3)将数组B逆置（得到 B^ -1）
(4)将逆置后的数组整体逆置（得到 (A^ -1 * B^ -1) ^-1 = BA）
下面开始用代码实现：
void reverse(int arr[],int from,int to) {
//数组移动的索引
int i = from, j = to;
//临时变量
int temp;
//开始将数组逆置
while (i < j)
{
//交换位置
temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
i++;
j--;
}
}
void leftMove(int arr[], int len, int p) {
if (arr == NULL || p <= 0 || p > len)
{
return;
}
//将数组A逆置
reverse(arr, 0, p - 1);
//将数组B逆置
reverse(arr, p, len - 1);
//将逆置后的数组整体逆置
reverse(arr, 0, len - 1);
//打印输出
cout << "数组向左移动" << p << "位的结果是：";
for (int i = 0; i < len; i++)
{
cout << arr[i] << " ";
}
cout << endl;
}测试：
int main() {
int arr0[] = { 1,5,3,24,8,7,34,23,4 };
cout << "数组移动前：";
for (int i = 0; i < 9; i++)
{
cout << arr0[i] << " ";
}
leftMoveArray(arr0, 9, 5);
int arr1[] = { 7,5,39,24,2,4,5 };
cout << "数组移动前：";
for (int i = 0; i < 7; i++)
{
cout << arr1[i] << " ";
}
cout << endl;
leftMove(arr1, 7, 2);
int arr2[] = { 1,5,3,24,8,7,5,64,34,23,4 };
cout << "数组移动前：";
for (int i = 0; i < 11; i++)
{
cout << arr2[i] << " ";
}
leftMove(arr2, 11, 8);
system("pause");
return 0;
}
容易知道该算法的时间复杂度为：O（n）,空间复杂度为：O（1），显然比第一种方法更优，更符合题目的要求。
由于笔者知识水平有限，出错再所难免，欢迎大家斧正。
