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