C语言轮转数组的三种实现

题目：

解法1：把最后一位数字移动到数组的第一位，然后将第二位开始的每一位往前移动一位

这种方法的时间复杂度=O（N^2）

空间复杂度=O（1）

rotate(int* arr, int n, int k)
{
	khttp://www.devze.com %= n;
	int i = 0;
	for (i = 0; i < k; i++)//旋转k次
	{
		int tmp = arr[n - 1];//把最后一个数拿出来赋给tmp
		//剩余元素整体向后移动
		int j = 0;
		for (j = n - 1; j > 0; j--)
		{
			arr[j] = arr[j - 1];编程客栈
		}
		arr[0] = tmp;//把最后一个值赋给数组的首元素处
	}
	int a = 0;
	for (a = 0; a < n; a++)
	{
		printf("%d", arr[a]);
	}
}
int main()
{
	int arr[10] = { 0,1,2,3,4,5,6,7,8,9 };
	int n = sizeof(arr) / sizeof(arr[0]);
	int k = 0;
	scanf("%d", &k);
	rotate(arr, n, k);
	return 0;
}

解法2：重新创建一个数组，把需要旋转的拿几个数字放在数组中，然后再把剩余的数放到这个新数组的后面

这种方法的时间复杂度=O（N）

空间复杂度=O（N）

void rotate(int* nums, int numsSize, int k) 
{
	int* tmp = (int*)malloc(sizeof(int) * numsSize);//开辟大小为n的动态内存
	k = k % numsSize;
	memcpy(tmp, nums + numsSize - k, sizeof(int) * k);//把旋转的数拷贝到新数组中
	memcpy(tmp+k, nums, sizeof(int) * (numsSize-k));//剩下的数拷贝到新数组的后面
	memcpy( nums,tmp,  sizeof(int) * numsSize);//把新数组拷贝给原来的数组
	free(tmp);
}

解法3：原地解决（三旋法）——最优法

这种方法的时间复杂度=O（N）

空间复杂度=O（1）

void reve(int arr[], int left, int right)//逆置函数，三个逆置都适用
{
	while (left < right)
	{
		int tmp = arr[left];
		arr[left] = arr[right];
		arr[right] = tmp;
		left++;
		right--;
	}
}
rotate(int* arr, int n, int k)
{
	k %= n;
	reve(arr, n - k, n - 1);//逆置后面的数
	reve(arr, 0, n - k - 1);//逆置前面的数
	reve(arr, 0, n - 1);//整体逆置
	int i = 0;
	for (i = 0; i < n; i++)
	{
	编程	printf("%d ", arr[i]);
	}
}
int main()
{
	int arr[10] = { 0,1,2,3,4,5,6,7,8,9 };
	int n = sizeof(arr) / sizeof(arr[0]);
	int k = 0uyHBeeEprv;
	scanf("%d", &k);
	rotate(arr, n, k);
	return 0;
}

 到此这篇关于C语言轮转数组的三种实现的文章就介绍到这了,更多相关C语言轮转数组内容请搜索编程客栈(www.devze.com)以前的文章或继续浏www.devze.com览下面的相关文章希望大家以后多多支持编程客栈(www.devze.com)！