面试-旋转数组的三种方法

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

方法一：

先编写右移一位的函数

//右移一位
void xuanzhuan1(int* nums, int n)
{
	assert(nums != NULL);
	int tmp = nums[n - 1];
	for(int i=n-1;i>0;i--)
	{
		nums[i] = nums[i - 1];
	}
	nums[0] = tmp;
}

}

再编写函数调用K次右移一位的函数

//右移k位
void Rotate(int* nums, int n, int k)
{
	assert(nums != NULL);
	if (k < 0)
	{
		return;
	}
	k = k % n;
	for (int i = 0; i < k; i++)
	{
		xuanzhuan1(nums, n);
	}
	

方法二：

申请新空间

将原来的数组分割成两个部分，直接向后移的，和往前移的，先把旋转到前面的写入到新申请的空间，后面补上向后移的，最后将新空间的内容依次赋值给原来的数组，然后释放申请的空间，并将指针置为空

void Rotate2(int* nums, int n, int k)
{
	assert(nums != NULL);
	if (k < 0)return;
	k = k % n;
	int* newdate = (int*)malloc(sizeof(int) * n);
	if (NULL == newdate)
	{
		exit(1);
	}
	int i = 0;
	for (int h = n - k; h < n; h++)
	{
		newdate[i++] = nums[h];
	}
	for (int j = 0; j < n - k; j++)
	{
		newdate[i++] = nums[j];
	}
	for (int i = 0; i < n; i++)
	{
		nums[i] = newdate[i];
	}
	free(newdate);
	newdate = NULL;

}

方法三：

逆置

先将数组全部逆置，然后把前k个元素和剩下的元素分别逆置

// 交换函数
void Swap_Int(int *p1,int *p2)
{
	int tmp;
	tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
//逆置函数
void Rev(int* nums, int left, int right)
{
	assert(nums != NULL);
	while (left < right)
	{
		Swap_Int(&nums[left], &nums[right]);
		left++;
		right--;
	}

}
//旋转函数
void Rotate3(int* nums, int n, int k)
{
	assert(nums != NULL);
	Rev(nums, 0, n - 1);
	Rev(nums, 0, k-1);
	Rev(nums, k, n - 1);
}