用一个长度为14的数组来储存给出的5张牌中每张牌出现的次数。
遍历数组,将出现的数字在计数数组中对应的位置加1,若其加1后大于2,切其本身不为0,则返回false。因两张不为joker的牌重复则不可能为顺子。遍历时记录出现的最大值与最小值。
遍历完后用最大值减去最小值,若大于4则返回false,因为五张牌不可能组成相差大于5的顺子。否则返回true。
这种解法只用到一重循环,时间复杂度为O(n)。
关于空间复杂度,虽然用到了辅助数组,但该数组的大小固定为14(14张扑克牌),所以我个人认为这里空间复杂度为O(1)。
class Solution {
public:
bool IsContinuous( vector<int> numbers ) {
vector<int> counter(14,0);
int max = 1;
int min = 14;
for(int i = 0; i < numbers.size();i++){
counter.at(numbers.at(i))++;
if(counter.at(numbers.at(i)) > 1 && numbers.at(i) != 0){
return false;
}
if(numbers.at(i) != 0 && numbers.at(i) < min){
min = numbers.at(i);
}
if(numbers.at(i) > max){
max = numbers.at(i);
}
}
if(max - min > 4){
return false;
}
return true;
}
};