快慢指针

数组中重复的数字

http://www.nowcoder.com/questionTerminal/623a5ac0ea5b4e5f95552655361ae0a8

O(1)空间,O(n)时间:

public class Solution {
    public boolean duplicate(int numbers[],int length,int [] duplication) {
        int sum = 0, n = 0;
        for(n = 0; n < length; ++n) sum += numbers[n];    //无重复就是等差求和
        if(sum == n*(n - 1)/2){
            duplication[0] = -1;
            return false;
        }
        //把下标当成next指针,数组变成链表,求环的入口
        int i = numbers[numbers[0]], j = numbers[numbers[numbers[0]]];//快慢指针
        while(i != j){    //指针i和j相遇时,j走了i的两倍,且j多走了任意个环
            i = numbers[i];    //指针i每次下移一个节点
            j = numbers[numbers[j]];    //指针j每次下移2个节点
        }
        int k = numbers[0];    //指针i已经走了任意个环,之后仍在环上转
        while(i != k){    //i与k一起走,必在环的入口相遇
            i = numbers[i];
            k = numbers[k];
        }
        duplication[0] = i;
        return true;
    }
}
全部评论

相关推荐

真心劝退测开,这个方向真的不适合普通人,尤其是应届生。我身边这一届同学的情况,说实话已经很说明问题了。后端秋招一开始确实难,但只要技术不是太拉,后面补录、加面、捞人的机会一波接一波,最后基本都能上岸中小厂。而那些一开始就冲测开的,很多到现在还在等消息,甚至直接凉了。最直观的感受就是:测开的坑真的少得可怜。同一批同学里,后端、前端、客户端基本都有大厂&nbsp;offer&nbsp;扎堆的情况,哪怕不是顶级大厂,也能拿到几个中厂保底。但测开呢?泡出来的又有多少呢。不是不努力,是岗位就那么点,连给你复活赛的机会都没有。后端还能互相捞。秋招挂了,春招、补录、内推、转组,总能找到出口。测开一旦挂了,基本就是真的挂了,后面连投的岗位都没几个。目前有些转的人可能拿了几个不错的实习offer,那到秋招呢?hc少就笑不出来了。现在测开也就只有大厂和顶中厂有,小厂就是测试点点点,大厂也很多是点点点,后端起码还有小厂保个底还有人幻想什么先测开再转开发,我只能说太天真了。测开的经历,想转后端或者客户端根本不可能。核心开发经验没有,项目深度不够,面试官一句那你为什么不一开始就做开发基本宣判死刑。反过来,后端、前端干不下去了,转测开却很容易,这已经说明问题了。如果你是普通双非,那更要慎重。测开&nbsp;HC&nbsp;本来就少,筛人还看背景,普通学校在这种极小池子里基本就是陪跑。你用一个最普通的简历,去抢最少的岗位,结果可想而知。再说客户端和前端。很多人看不起前端,觉得卷,觉得不高级,但现实是岗位多、需求稳定、HC&nbsp;实在。客户端更不用说,Android&nbsp;和&nbsp;iOS&nbsp;到现在依然是硬需求,技术路线清晰,工程经验越久越值钱。我身边拿到大厂最多的,反而是客户端和前端,而不是测开。说句难听的,测开不是不能干,但那是给已经没得选的人准备的退路,不是给应届生拿来当首选的。秋招无脑选测开,本质就是用短期好像更容易上岸,换长期被动甚至被锁死。我是真心建议,能选客户端和前端就选客户端前端,再不行就去后端,哪怕多投多卷一点,也比一头扎进测开强得多。等你真正经历一轮秋招、春招、补录之后,就会发现被反复捞的,从来不是测开劝退不是唱衰,是不想看更多人踩已经踩烂的坑。
Java抽象小篮子:这话术换成劝退后端开发一点问题也没有,总有小登冲出来说别人想焊死车门,我寻思车门要真这么容易焊丝还轮得到你们上车吗
计算机有哪些岗位值得去?
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务