实现数组左移

发布于 2020-07-21  244 次阅读


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


繁华落尽,雪花漫天飞舞。