单页面网站可以做自适应网站吗,中山百度首页推广,网页美术设计主要学什么,学校网站设计一个算法#xff0c;把一个含有N个元素的数组循环右移K位#xff0c;要求时间复杂度为O#xff08;N#xff09;#xff0c;且只允许使用两个附加变量。 不合题意的解法如下#xff1a; 我们先试验简单的办法#xff0c;可以每次将数组中的元素右移一位#xff0c;… 设计一个算法把一个含有N个元素的数组循环右移K位要求时间复杂度为ON且只允许使用两个附加变量。 不合题意的解法如下 我们先试验简单的办法可以每次将数组中的元素右移一位循环K次。abcd1234---4abcd123---34abcd12---234abcd1---1234abcd。代码如下所示 [cpp] view plaincopy RightShift(int *arr, int N, int K) { while(K--) { int t arr[N - 1]; for(int i N - 1 ; i 0 ; i--) { arr[i] arr[i - 1]; } arr[0] t; } } 虽然这个算法可以实现数组的循环右移但是算法复杂度为OK*N不符合题目的要求要继续探索。 分析与解法 假如数组为abcd1234循环右移4位的话我们希望达到的状态是1234abcd。不妨设K是一个非负的整数当K为负整数的时候右移K位相当于左移-K位左移和右移在本质上是一样的。 解法一 大家开始可能会有这样的潜在假设KN。事实上很多时候也的确是这样的。但严格来说我们不能用这样的“惯性思维”来思考问题。尤其在编程的时候全面地考虑问题是很重要的K可能是一个远大于N的整数在这个时候上面的解法是需要改进的。 仔细观察循环右移的特点不难发现每个元素右移N位后都会回到自己的位置上。因此如果KN右移K-N以后的数组序列跟右移K位的结果是一样的。进而可得出一条通用的规律右移K位之后的情形跟右移K’K%N位之后的情形一样代码如下所示 [cpp] view plaincopy RightShift(int *arr, int N, int K) { K K % N ; while(K--) { int t arr[N - 1]; for(int i N - 1 ; i 0 ; i--) { arr[i] arr[i - 1]; } arr[0] t; } } 可见增加考虑循环右移的特点之后算法复杂度降为ON^2这跟K无关与题目的要求又接近了一步。但时间复杂度还不够低接下来让我们继续挖掘循环右移前后数组之间的关联。 解法二 我们还是把字符串看成有两段组成的记位XY。左旋转相当于要把字符串XY变成YX。我们先在字符串上定义一种翻转的操作就是翻转字符串中字符的先后顺序。把X翻转后记为XT。显然有(XT)TX。 我们首先对X和Y两段分别进行翻转操作这样就能得到XTYT。接着再对XTYT进行翻转操作得到(XTYT)T(YT)T(XT)TYX。正好是我们期待的结果。 分析到这里我们再回到原来的题目。我们要做的仅仅是把字符串分成两段第一段为前面m个字符其余的字符分到第二段。再定义一个翻转字符串的函数按照前面的步骤翻转三次就行了。时间复杂度和空间复杂度都合乎要求。 假设原数组序列为abcd1234要求变换成的数组序列为1234abcd即循环右移了4位。比较之后不难看出其中有两段的顺序是不变的1234和abcd可把这两段看成两个整体右移K位的过程就是把数组的两部分交换一下变换的过程通过一下步骤完成 1、逆序排列abcdabcd1234---dcba1234 2、逆序排列1234dcba1234---dcba4321 3、全部逆序dcba4321---1234abcd。 代码如下所示 [cpp] view plaincopy Reverse(int *arr, int b, int e) //逆序排列 { for( ; b e; b, e--) //从数组的前、后一起遍历 { int temp arr[e]; arr[e] arr[b]; arr[b] temp; } } RightShift(int *arr, int N, int K) { K K % N ; Reverse(arr, 0, N-K-1); //前面N-K部分逆序 Reverse(arr, N-K, N-1); //后面K部分逆序 Reverse(arr, 0, N-1); //全部逆序 } 这样我们就可以在线性时间内实现右移操作了。 转载于:https://www.cnblogs.com/zhanglanyun/archive/2012/08/16/2642927.html
