模拟写法,时间复杂度Onlogn,花在快排身上。
bool IsContinuous(vector<int>& numbers) {
if(numbers.size() == 0) return false;
sort(numbers.begin(), numbers.end());
int cnt = 0;
// 统计赖子个数
for(auto & i : numbers){
if(i == 0) cnt++;
}
for(int i = 0; i < numbers.size() - 1; i++){
if(numbers[i] == 0) continue;
if(numbers[i + 1] == numbers[i]) return false; // 有重复牌肯定不可能是顺子
int gap = numbers[i + 1] - numbers[i] - 1;
if(gap > cnt) return false; // 赖子不够填
else cnt -= gap;
}
return true;
}
也可以用集合遍历,时间复杂度为On
1、遍历五张牌,遇到大小王(即 0 )直接跳过。
2、判别重复: 利用 Set 实现遍历判重, Set 的查找方法的时间复杂度为 O(1) ;
3、获取最大 / 最小的牌: 借助辅助变量 ma 和 mi ,遍历统计即可。
贴个python代码:
class Solution:
def IsContinuous(self, numbers):
# write code here
repeat = set()
ma, mi = 0, 14
for num in numbers:
if num == 0: continue # 跳过大小王
ma = max(ma, num) # 最大牌
mi = min(mi, num) # 最小牌
if num in repeat: return False # 若有重复,提前返回 false
repeat.add(num) # 添加牌至 Set
return ma - mi < 5 # 最大牌 - 最小牌 < 5 则可构成顺子