数组右移K位的思考

54 阅读 0 评论 36 点赞

我是靠谱客的博主大胆玫瑰，最近开发中收集的这篇文章主要介绍数组右移K位的思考，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

和朋友聊天,偶然聊到了数组右移的算法,不禁想起了某个大牛的三次翻转法,绝对是个经典的算法.正好今天没事,就静下心想想,还有什么更好的算法吗?

首先能想到的就是每次右移一个,需要右移几个就执行几次就好了,假设数组长度为N,右移数为K,则时间复杂度O(N*K),但这种方法好理解,一看就明白!

相关的算法也简单:

void LoopMove(int arr[], int count, int k)
{
	//空间O(1),时间(K*N)
	int i, j,t;
	for(i=0;i<k;i++)
	{
		t = arr[count - 1];
		for (j = count - 1; j > 0; j--)
		{
			arr[j] = arr[j - 1];
		}
		arr[0] = t;
	}
}

然后就是大神级别的三次翻转法,将前面N-K个元素翻转,后面的K个元素翻转,最终整体翻转,时间复杂度O(N),空间复杂度O(1),确实牛!

实现代码也简单:

void Reverse(int arr[], int count)
{
	int i = 0;
	int j = count - 1;
	int t;
	while (i < j)
	{
		t = arr[i];
		arr[i] = arr[j];
		arr[j] = t;
		i++;
		j--;
	}
}

void ThreeReverse(int arr[], int count, int k)
{
	//空间O(1),时间O(N)
	Reverse(arr, count - k);
	Reverse(&arr[count - k ], k);
	Reverse(arr, count);
}

Reverse函数完成翻转,ThreeReverse函数设置完成3次翻转

三次翻转确实很不错了,能不能在优化一下?我想时间复杂度已经是O(N)了,不好弄,空间复杂度也O(1),也不好弄,能不能另辟蹊径?

俗话说,最直接的也许就是最好的,基于这种想法,尝试了下面的一个算法,暂时称之为空位算法吧.思想很简单,很直接,上图:

就是先把1存起来,7就可以放到1的未知,然后7的未知变为空位,就可以把4移到7的未知,依次下去,直到需要将最开始1需要安置时就结束了,然后把1安置好.

算法实现如下:

void HoveringPoint(int arr[], int count, int k)
{
	//满足了空间O(1),时间O(N)
	k = k % count;
	int t = arr[0];
	int c = 0,n;
	while(n=(c+count-k)%count)
	{
		arr[c] = arr[n];
		c = n;
	}
	arr[c] = t;
}

上面的代码貌似解决了问题，但实际上有一个很大的bug，如果移动的位数和数组长度的最大公约数不为1呢？这时候就会出现只有第一个相关的数据被移动，后面的2，3....都没动啊，所以，上面的代码还需要完善一下，如下：

void HoveringPoint(int arr[], int count, int k)
{
	//满足了空间O(1),时间O(N)
	k = k % count;
	if (k == 0) {
		return;
	}
	//求最大公约数
	int m = k;	//假定最大公约数为k
	int s = count;
	while (s % m )
	{
		int tmp = m;
		m = s % m;
		s = tmp;
	}
	
	//从0到最大公约数-1进行循环，确保每个数据都被循环到
	for (int i = 0; i < m; i++)
	{
		int t = arr[i];
		int c = i, n;
		while ((n = (c + count - k) % count) !=i)
		{
			arr[c] = arr[n];
			c = n;
		}
		arr[c] = t;
	}
}

我们找到最大公约数，并对从0到最大公约数-1的每一个位置都按照上面移动的逻辑处理就好了。

最后,把整体代码贴给大家,有要测试的小伙伴可以测试下啊!

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>

void print(int arr[],int count)
{
	int i;
	for (i = 0; i < count; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("n");
}


void LoopMove(int arr[], int count, int k)
{
	//空间O(1),时间(K*N)
	int i, j,t;
	for(i=0;i<k;i++)
	{
		t = arr[count - 1];
		for (j = count - 1; j > 0; j--)
		{
			arr[j] = arr[j - 1];
		}
		arr[0] = t;
	}
}

void Reverse(int arr[], int count)
{
	int i = 0;
	int j = count - 1;
	int t;
	while (i < j)
	{
		t = arr[i];
		arr[i] = arr[j];
		arr[j] = t;
		i++;
		j--;
	}
}

void ThreeReverse(int arr[], int count, int k)
{
	//空间O(1),时间O(N)
	Reverse(arr, count - k);
	Reverse(&arr[count - k ], k);
	Reverse(arr, count);
}

void HoveringPoint(int arr[], int count, int k)
{
	//满足了空间O(1),时间O(N)
	k = k % count;
	if (k == 0) {
		return;
	}
	//求最大公约数
	int m = k;	//假定最大公约数为k
	int s = count;
	while (s % m )
	{
		int tmp = m;
		m = s % m;
		s = tmp;
	}
	
	//从0到最大公约数-1进行循环，确保每个数据都被循环到
	for (int i = 0; i < m; i++)
	{
		int t = arr[i];
		int c = i, n;
		while ((n = (c + count - k) % count) !=i)
		{
			arr[c] = arr[n];
			c = n;
		}
		arr[c] = t;
	}
}

//必须满足空间O(1)
int main()
{
	int arr[] = { 1,2,3,4,5,6,7 };
	int k = 3;
	int count = sizeof(arr) / sizeof(arr[0]);
	HoveringPoint(arr, count, k);
	print(arr, count);
	return 0;
}