文档章节

数组循环移位

laoyao
 laoyao
发布于 2014/04/07 11:54
字数 555
阅读 1628
收藏 32

看到这个题目,一般是先实现题目意思再说,一般我们按照正常思路解题,将数组元素循环右移,比如abcd1234,假若循环四位,就是4abcd123->34abd12->234abcd1->1234abcd,这样的话代码很简单:

RightShift(int [] arr,int N,int K){
    while(K--){
        int t = arr[N-1];
        for(int i = N-1;i>0; i--){
        }
        arr[0] = t;
    }
}

这样写是可以实现循环向右移动,但是这样的时间复杂度实O(N * K),是不符合题目要求的。那么还需要别的解法。

我们通过观察看以看到,数组abcd234向右移动K位,相当于向左移动-K位,向右移动跟向左移动本质上是一样的。

在考虑解题的同时,我们应该想到的是K的取值是可以大于N的,不要让惯性思维束缚了我们的大脑,假若K>N,那么数组向右移动4位跟向右移动12位,20,28是等同的,那么我们可以先做一个处理,K=K%N,这样我们的代码就变成了:

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[0] = t;
    }
}

这样结果的话,运算的时间复杂度变成了O(N * N ),时间复杂度降低了,但是还不符合题目要求;,继续探索

假如abcd234向右移动四位的话,我们可以发现其实是abcd跟1234兑换了一下,把两部分分别看成一个整体,然后兑换,具体步骤如下:

1、abcd倒叙->dcba1234

2、1234倒叙->dcba4321

3、全部倒叙->1234abcd

按照这个思路写代码的话就变成了如下结果:

ReghtShift(int [] arr,int N,int K){
    K%=N;
    Reverse(int [] arr,0,N-k-1);
    Reverse(int [] arr,N-K,N-1);
    Reverse(int [] arr,0,N-1);
}

Reverse(int [] arr,int b,int e){
    for(;b<e;b++,e--){
        int temp = arr[e];
            arr[e] = arr[b];
            arr[b] = temp;
    }
}

这样的话就可以在线性时间内实现向右移动操作了

© 著作权归作者所有

laoyao
粉丝 7
博文 22
码字总数 28605
作品 0
芜湖
程序员
私信 提问
加载中

评论(8)

ericsoul
ericsoul
lz的例子举得不好。n=2k。直接导致最后一种没看懂。另外最后一种算折半,时间复杂度是log2n吧(没看懂,所以不确定,从结构上像)。另外,为什么我的直觉是n的复杂度,而不是k*n或者n*n呢?既然最后一种可行的话,一次就移动k的位置不行么(当然,考虑k>n,先求摩)?t=a0,a0=a3,a3=a1,a1=a4,a4=a2,a2=a5……。更好就是直接再开一个k或者n的数组。
laoyao
laoyao 博主

引用来自“YSYANG”的评论

可以求c 版数据结构电子版嘛??

这是在编程之美上看的。然后整理了下。没有C版数据结构电子版的,抱歉哈

YSYANG
YSYANG
c加加 总是没显出来
YSYANG
YSYANG
c 版
YSYANG
YSYANG
可以求c 版数据结构电子版嘛??
laoyao
laoyao 博主

引用来自“尹凌风”的评论

解说不错,代码应该是c++版数据结构上的吧

我在看编程之美,顺便总结下,算是学习笔记吧
尹凌风
尹凌风
解说不错,代码应该是c++版数据结构上的吧
v
vincent_os
*ptr++的计算过程(ptr是一个二维指针)

指向指针数组的指针 指针的指针另一用法是处理指针数组。有些程序员喜欢用指针数组来代替多维数组,一个常见的用法就是处理字符串。 #include<iostream> include<cstdio> using namespace s...

zray4u
2016/07/13
38
0
数据结构与算法9-简单排序-选择排序

选择排序改进了冒泡排序,将必要交换次数从O(N^2)减少到O(N),不幸的是比较次数仍保持为O(N^2),然而,大量记录需要在内存中移动,这就使得交换的时间更为重要。 外层循环用循环变量o...

沉迷于编程的小菜菜
2018/07/26
0
0
Lintcode39 Recover Rotated Sorted Array solution 题解

【题目描述】 Given a rotated sorted array, recover it to sorted array in-place. 给定一个旋转排序数组,在原地恢复其排序。 【题目链接】 http://www.lintcode.com/en/problem/recover...

abcdd1234567890
2018/06/29
0
0
移位排序算法--从赛跑想到的

说到排序,可能你能说出一大堆,什么冒泡,快速,插入,希尔...说实话,我能轻易写出那些算法,但是总觉得没有什么意义,人的脑子里净装一些书上的东 西,还不如去当图书馆管理员呢?于是我就...

晨曦之光
2012/04/10
142
0
java技巧--提高代码运行效率

1.尽量在合适的场合使用单例 使用单例可以减轻加载的负担,缩短加载的时间,提高加载的效率,但并不是所有地方都适用于单例,简单来说,单例主要适用于以下三个方面 第一,控制资源的使用,通...

漠、
2012/06/05
391
1

没有更多内容

加载失败,请刷新页面

加载更多

nginx学习笔记

中间件位于客户机/ 服务器的操作系统之上,管理计算机资源和网络通讯。 是连接两个独立应用程序或独立系统的软件。 web请求通过中间件可以直接调用操作系统,也可以经过中间件把请求分发到多...

码农实战
今天
5
0
Spring Security 实战干货:玩转自定义登录

1. 前言 前面的关于 Spring Security 相关的文章只是一个预热。为了接下来更好的实战,如果你错过了请从 Spring Security 实战系列 开始。安全访问的第一步就是认证(Authentication),认证...

码农小胖哥
今天
12
0
JAVA 实现雪花算法生成唯一订单号工具类

import lombok.SneakyThrows;import lombok.extern.slf4j.Slf4j;import java.util.Calendar;/** * Default distributed primary key generator. * * <p> * Use snowflake......

huangkejie
昨天
12
0
PhotoShop 色调:RGB/CMYK 颜色模式

一·、 RGB : 三原色:红绿蓝 1.通道:通道中的红绿蓝通道分别对应的是红绿蓝三种原色(RGB)的显示范围 1.差值模式能模拟三种原色叠加之后的效果 2.添加-颜色曲线:调整图像RGB颜色----R色增强...

东方墨天
昨天
11
1
将博客搬至CSDN

将博客搬至CSDN

算法与编程之美
昨天
13
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部