0%

【算法思想】循环移动一个数组

问题:如何将一个数组循环左移或者右移k位?

在下面的解决方案中,我们以循环左移为例。 我们最容易想到的是,将前k个元素复制到一个临时的数组中,然后将剩下的n-k个元素向左移动k个位置,然后将之前的k个元素复制到剩下的位置。这种方法使用了k个额外的存储空间。我们想到到另一种方法是,只借助一个临时空间,每次只向左移动1位,循环k次。这种方法产生了多于的运行时间。前面一篇文章中用程序实现了循环右移一个数组的算法。前面提到的都是比较常规的算法,下面从其它角度来考虑这一问题:

循环数组x其实就是交换数组x的子数组a、b得到b、a。例如假设数组x为int x[]={1,2,3,4,5,6,7,8,9,10}; int a[]={1,2,3,4,5}; int b[]={6,7,8,9,10};那么将x循环左移5位则是x1={6,7,8,9,10,1,2,3,4,5};显然就将数组a,b交换后进行拼接在一起。当然这里举的是特例,是为了方便理解。下面是一般情况的分析:假设数组x为int x[]={1,2,3,4,5,6,7,8,9,10}; int a[]={1,2,3,}; int b[]={4,5,6,7,8,9,10};那么将x循环左移3位则是x1={4,5,6,7,8,9,10,1,2,3};因此移动k位,我们就假设a的大小是k位,剩下是b。如果直接交换,那就和上面提到的第一中方法一样了。下面是一种新的交换方法:这里假设a的元素比b少,则将b分为两个数组bl,br,其中br与a长度相同,bl为b的左边部分,br为b的右边部分。在上面例子中,bl={4,5,6,7},br={8,9,10}。

则数组x是由a,bl,br拼接而成。经过左移k位后,结果数组x1是由bl,br,a拼接而成。因此这里需要进行两步交换,首先a与br交换,变成br,bl,a;然后br与bl交换,变成bl,br,a。

上面问题的重中之重是进行交换。我们还可以这样进行交换:我们定义a={1,2,3}的反为a’{3,2,1}。那么由ab变成ba,可以通过(a’b’)’得到。因此我们可以写一个求反的子函数,用于求数组中特定部分元素的反。先对a求反,再对b求反,最后对整体求反,就可以得到结果。这里需要调用求反子函数3次即可。

本文提到的方法较常规的方法的优点是不用计算移动k位后应该到达的位置。本文提到的方法并不是最好的方法,只是说明我们可以这么做,遇见一个问题,我们可以找到多种方法解决。本文主要是介绍一种思路,程序比较简单,就不具体实现了。

坚持原创技术分享,您的支持将鼓励我继续创作!