连续性史上最优解

扑克牌顺子

http://www.nowcoder.com/questionTerminal/762836f4d43d43ca9deb273b3de8e1f4

可以充分利用该题的特性来到达时间复杂度为n,空间复杂度为1的目的
判断输入的数组元素是否连续,并且元素个数为5个,1-n,若出现0,则0可以充当任何数
先看一下没有0出现的情况,如果连续的话,最大数和最小数相差就为4(因为元素有5个),max - min = 4
如果出现0,最大值与最小值之差小于4,则说明0可以代替 大的数,所以让max 加一;最大值与最小值的差值大于5,说明0可以代替小的,让max 减一来达到0代替的效果;这样最后可以达到在连续的情况下max - min = 4

    public boolean isContinuous(int [] numbers) {
        if(numbers == null || numbers.length<5) return false;
        int max = numbers[0], min = numbers[0];
        // 先找出最大值 和 最小值
        for(int num:numbers) {
            if(max < num && num != 0) {
                max = num;
            }
            if ((min > num && num != 0) || min == 0) {
                min = num;
            }
        }
        // 用0补充
        for(int num:numbers) {
            if(num == 0) {
                if(max - min > 5) {
                    max --;
                } else if (max - min < 4) max ++;
            }
        }
        return (max - min) == 4;
    }

时间复杂度:O(N)
空间复杂度:O(1)

ps:该方法只使用于除0外没有重复元素出现,如{0,3,3,6,4},还是会返回true,但是本题用例貌似都没有重复元素的,所以可以AC
其实本题最多出现两个0,所以第一次循环的时候统计一下0的个数,后面用0补充用不着再遍历一遍

全部评论

相关推荐

05-12 11:09
已编辑
门头沟学院 后端
已注销:没必要放这么多专业技能的描述。这些应该是默认已会的,写这么多行感觉在凑内容。项目这块感觉再包装包装吧,换个名字,虽然大家的项目基本都是网上套壳的,但是你这也太明显了。放一个业务项目,再放一个技术项目。技术项目,例如中间件的一些扩展和尝试。
点赞 评论 收藏
分享
真烦好烦真烦:牛友太有实力了
点赞 评论 收藏
分享
06-27 18:45
中山大学 Ruby
25届应届毕业生,来广州2个礼拜了,找不到工作,绝望了,太难过了…
应届想染班味:9爷找不到工作只能说明,太摆了或者太挑了。
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

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