下面请看一道算法题:
设将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),显然比第一种方法更优,更符合题目的要求。
由于笔者知识水平有限,出错再所难免,欢迎大家斧正。