【程序设计】旋转数组

良木生香

发布于 2026-01-09 14:18:47

980

今天在力扣平台上看到一道有意思的题目：189. 轮转数组 - 力扣（LeetCode）

根据题目要求，是将数组里面的元素进行k次旋转，这道题有多种解法，现在我们就来探讨一下：

解法一：暴力法

#include<stdio.h>

void rotate(int* num, int numSize, int k)
{
	
	while (k--)
	{
		int temp = num[numSize - 1];  //先将最后的数据用第三变量存起来
		for (int i = numSize - 1; i > 0; i--)
		{
			num[i] = num[i - 1];
		}
		num[0] = temp;   //当其他数据移动好位置之后再将原本最后一个数据放到第一个位置上
	} 
}

int main()
{
	int num[100005] = { 0 };
	int numSize = 0;
	int k = 0;
	scanf("%d", &numSize);
	for (int i = 0; i < numSize; i++)
	{
		scanf("%d", num + i);//一次输入数组数据
	}
	scanf("%d", &k);    //输入旋转的次数
	rotate(num, numSize, k);  //进行旋转操作
	for (int i = 0; i < numSize; i++)
	{
		printf("%d ", *(num + i));
	}
	return 0;
}

代码运行的结果如下：

可见这个代码是实现了我们想要的功能，提交看看是不是真的可以通过？

提交之后，我们可以看到：

居然超出了时间限制！！！，那可咋办？不慌，我们先通过时间复杂度来分析一下：

我们代码的时间复杂度主要是在旋转函数中，根据观察可以得出，旋转函数的时间复杂度为O(k*numSize)，当k==numSize时，时间复杂度可以看成O(numSize^2),这就是一个非常大的数字了，这不超时才怪咧，那我们要怎么优化呢？

解法二：临时数组

我们可以用一个临时数组来存放原数组数据移动之后的状态，再将临时数组中的数据放回原数组，大家可以参考下图来辅助理解：

献上代码：

#include<stdio.h>

void totate(int* num, int numSize, int k)
{
	int temp[100005] = { 0 };   //定义一个临时数组
	for (int i = 0; i < numSize; i++)
	{
		int index = (i + k) % numSize;
		temp[index] = num[i];     //将旋转后的数据状态放进临时数组中
	}
	for (int i = 0; i < numSize; i++)
	{
		num[i] = temp[i];   //再从临时数组中复制数据到原数组
	}
}


int main()
{
	int numSize = 0;
	int num[100005] = { 0 };
	int k = 0;
	scanf("%d", &numSize);
	for (int i = 0; i < numSize; i++)
	{
		scanf("%d", num + i);
	}
	scanf("%d", &k);
	rotate(num, numSize, k);
	for (int i = 0; i < numSize; i++)
	{
		printf("%d ", *(num + i));
	}
	return 0;
}

在编译器上的运行结果为：

由此可见，程序的功能是被完美实现了，那再提交到力扣上面看看能不能通过:

当然，对于创建临时数组这个方法，还有第二种写法，那就是使用malloc函数创建数组,代码如下：

#include<stdio.h>
#include<stdlib.h>



void rotate(int* num, int numSize, int k)
{
	//先跟内存申请一块空间，创建一个新的数组
	int* new_num_arr = (int*)malloc(sizeof(num));
	if (new_num_arr == NULL)
	{
		return;
	}

	//申请成功，那就将原来数组里的数据按照移动后的位置放进临时数组里
	for (int i = 0; i < numSize; i++)
	{
		int index = (i + k) % numSize;//这个是数据移动之后的应该在的下标位置
		*(new_num_arr + index) = *(num + i);  //将原数组的数据复制到临时数组中
	}

	//复制完成之后，再将临时数组中的数据复制回原数组
	for (int i = 0; i < numSize; i++)
	{
		*(num + i) = *(new_num_arr + i);
	}
}

int main()
{
	int numSize = 0;
	int num[100005] = { 0 };
	int k = 0;
	scanf("%d", &numSize);
	for (int i = 0; i < numSize; i++)
	{
		scanf("%d", num + i);
	}
	scanf("%d", &k);
	rotate(num, numSize, k);
	for (int i = 0; i < numSize; i++)
	{
		printf("%d ", *(num + i));
	}
	return 0;
}

这样看，是通过了，说明这次的时间复杂度要比之前低，运行效率提升了，但是，根据力扣反馈回来的数据，可见我们目前的代码依旧是不算得优秀，那还能怎么修改代码呢？

解法三：使用三次反转

既然想要实现旋转的功能，那我们可以把旋转分为三步走，详情请看下图：

既然我们有了思路，那就用diamagnetic实现一下吧~：

#include<stdio.h>

//现创建一个反转函数：
void reverse(int* begin, int* end)
{
	while (begin < end)
	{
		//这里使用按位异或的方式将两个数进行交换
		*begin = *begin ^ *end;
		*end = *begin ^ *end;
		*begin = *begin ^ *end;

		//也可以使用传统的方法机进行交换：
		/*
        int* temp = NULL;
		temp = *begin;
		*begin = *end;
		*end = temp;
        */
		begin++;
		end--;
	}
}

//现在实现旋转函数：
void rotate(int* num, int numSize, int k)
{
	int reverse_time = k % numSize;
	reverse(num + (numSize - reverse_time), num + (numSize - 1));  //现将数组最后k个数字进行反转
	reverse(num, num + (numSize - reverse_time-1));   //再将前numSize-1个数字进行反转
	reverse(num, num + numSize-1);   //最后将整个数组进行反转
}

int main()
{
	int num[100005] = { 0 };
	int numSize = 0;
	int k = 0;
	scanf("%d", &numSize);
	for (int i = 0; i < numSize; i++)
	{
		scanf("%d", num + i);
	}
	scanf("%d", &k);

	//现在使用函数：
	rotate(num, numSize, k);
	for (int i = 0; i < numSize; i++)
	{
		printf("%d ", *(num + i));
	}
	return 0;
}

运行结果如下：