题意理解
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;
}
};时间复杂度:。排序的时间为
,之后遍历一遍数组。
空间复杂度:。没有开辟任何新的空间。

京公网安备 11010502036488号