连续性史上最优解
扑克牌顺子
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补充用不着再遍历一遍