题意理解
5张扑克牌对应5个数,包含0~13。其中0可以表示1~13之间的任意数字。判断这5个数字是否连成1~13之内的顺子。
方法一
对于5个数字是否能连成顺子,主要观察两方面:
(1)如果有重复的数字(0除外),则必然不可能连成顺子。
(2)如果最大值和最小值(0除外)的差大于等于5,则必然不可能连成顺子。(3个数填不满中间的间隔)
对于算法的正确性:
在满足条件1的情况下,假设存在i(i<5)个0,对于剩下5-i个数,如果满足条件2,即它们的极差为(4-i)~4。
当极差为4的时候,把i个0填在中间;
当极差变小的时候,i个0一部分填在中间,一部分填在max或者min的外侧即可。(因为数组长度为5,远小于13,所以如果max为13,则min外侧可用0代替;如果min是1,则max外侧可用0代替)。
示意图如下:
具体代码如下:
class Solution { public: bool IsContinuous( vector<int> numbers ) { vector<int> exist(14,-1);//定义一个数组用来判断某个数字是否出现过 int minm = 14, maxm = -1; //遍历数组,找到最值 for (int i=0;i<numbers.size();i++) { if (numbers[i] == 0) { continue; } if (exist[numbers[i]] != -1) return false; exist[numbers[i]] = 1; if (minm > numbers[i]) minm = numbers[i]; if (maxm < numbers[i]) maxm = numbers[i]; } if (maxm - minm < 5) return true; return false; } };
时间复杂度:。只是遍历了一遍数组。
空间复杂度:。创建了新数组exist,用来记录数字是否有重复的情况。
方法二
对数组进行排序,找出最值,注意要排除0。同样是根据方法一中的两个条件进行判断。
注意,排序之后如果出现重复的情况,则重复的两个数必然是相邻的。
具体代码如下:
class Solution { public: bool IsContinuous( vector<int> numbers ) { sort(numbers.begin(), numbers.end()); int index = 0;// index记录第一个非0数值出现的位置 for (int h=0; h<numbers.size(); h++) { if (!numbers[h]) { index++; continue; } //注意范围不能越界.&&的先后顺序不能错 if (h<numbers.size()-1 && numbers[h] == numbers[h+1]) return false; } //判断极差的大小 if (numbers.back() - numbers[index] <= 4) { return true; } else return false; } };
时间复杂度:。排序的时间为,之后遍历一遍数组。
空间复杂度:。没有开辟任何新的空间。