算法思路一:集合set + 遍历

解题思路:

根据题意,此 55 张牌是顺子的 充分条件 如下:
    除大小王外,所有牌 无重复 ;
    设此 55 张牌中最大的牌为 max ,最小的牌为 min (大小王除外),则需满足
                                                                       max - min < 5
算法:
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 则可构成顺子

复杂度分析:

时间复杂度O(N):其中 N 为 numbers 长度,本题中 N≡5 ;遍历数组使用 O(N) 时间。
空间复杂度O(N):用于判重的辅助 Set 使用 O(N) 额外空间

算法思路二:排序 + 遍历

解题思路:

算法流程:
1、先对数组执行排序。
2、判别重复: 排序数组中的相同元素位置相邻,因此可通过遍历数组,判断 nums[i]=nums[i+1] 是否成立来判重。
3、获取最大 / 最小的牌: 排序后,数组末位元素nums[4] 为最大牌;元素 nums[joker] 为最小牌,其中 joker 为大小王的数量。

图解:

代码展示:

JAVA版本
import java.util.Arrays;

public class Solution {
    public boolean IsContinuous(int [] numbers) {
        int joker = 0;
        Arrays.sort(numbers); // 数组排序
        for(int i = 0; i < 4; i++) {
            if(numbers[i] == 0) joker++; // 统计大小王数量
            else if(numbers[i] == numbers[i + 1]) return false; // 若有重复,提前返回 false
        }
        return numbers[4] - numbers[joker] < 5; // 最大牌 - 最小牌 < 5 则可构成顺子
    }
}

复杂度分析:

时间复杂度O(NlogN):其中 N 为 numbers 长度,本题中 N≡5 ;数组排序使用O(NlogN)时间
空间复杂度O(1):采用一个变量使用O(1)大小额外空间