旋转数组问题

题目描述

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

方法一：

分析：

一个数组【1，2，3，4，5，6，7】如果旋转3次，得到的数组就是【5，6，7，1，2，3，4】。方法一是最好想的方法。我们一次一次旋转数组，每次都把数组中最后一个元素放到第一个位置，把剩余的元素都向后挪动一个位置。重复k次操作，就得到了结果。

代码实现

void change(int* arr, int size)   //每次旋转一次
{
	int tmp = arr[size - 1];    //保存最后一个元素
	int i = 0;
	for (i = size-2; i >= 0; i--)  //将剩余元素全部向挪动一位
	{
		arr[i + 1] = arr[i];
	}
	arr[0] = tmp;                //将原来最后位置的数放到第一位
}
void change_sort(int*arr, int size, int k)   //arr-数组   size-数组元素个数   k-旋转次数
{
	for (int i = 0; i < k; i++)              //旋转k次
	{
		change(arr, size);
	}
}

劣势：

这种方法的时间复杂度为O（k*n）所以说是不高效的

方法二：

分析：

我们可以重新开辟一块空间，将原数组的数据按照旋转之后的移动下来，再把数据拷贝回去

代码实现

int main()
{
	int k = 3;
	int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
	int sz = sizeof(arr) / sizeof(arr[0]);  //sz-数组元素个数
	int* a = (int*)malloc(sz*sizeof(int));  //新开辟一块空间
	int i = 0;
	for (i = 0; i < sz - k; i++)               //将arr中前sz-k个元素放在a的后面
	{                        
		a[k + i] = arr[i];   //arr->0~k-sz-1      //a->k~sz-1   (下标)
	}
	for (i = 0; i < k; i++)                    //将arr中后k个元素放在a的前面
	{
		a[i] = arr[sz-k+i];  //arr->sz-k~sz-1     //a->0~k-1    (下标)
	}
	for (i = 0; i < sz; i++)
		arr[i] = a[i];                     //最后将数组拷贝回去
	return 0;
}

劣势：

需要重新开辟一块空间，空间复杂度为O(N)

方法三：

分析：

将数组分为前n-k个和后n个，分别将该两部分逆置，再将整个数组逆置，即可得到最后结果。

代码实现：

void reverse(int*arr, int left, int right)
{
	while (left < right)   //不断交换头尾两端数据
	{
		int tmp = arr[left];
		arr[left] = arr[right];
		arr[right] = tmp;
		left++;
		right--;
	}
}

int main()
{
	int k = 3;
	int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
	int sz = sizeof(arr) / sizeof(arr[0]);  //求元素个数
	reverse(arr,0,sz-k-1);   //逆置前sz-k个数据
	reverse(arr,sz-k,sz-1);  //逆置后k个数据
	reverse(arr,0,sz-1);     //整体逆置
	return 0;
}

优势：

时间复杂度为O（N），空间复杂度为O（1）所以比上面两种方法都高效