连续性史上最优解

扑克牌顺子

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补充用不着再遍历一遍

全部评论

相关推荐

11-27 17:08
已编辑
牛客_产品运营部_私域运营
腾讯 普通offer 24k~26k * 15,年包在36w~39w左右。
点赞 评论 收藏
分享
牛客868257804号:九个中铁八个中建
点赞 评论 收藏
分享
挣K存W养DOG:入职送金条全球游,路过缅甸停一下🐔
点赞 评论 收藏
分享
评论
2
收藏
分享
牛客网
牛客企业服务