题解 | #扑克牌顺子#
扑克牌顺子
http://www.nowcoder.com/practice/762836f4d43d43ca9deb273b3de8e1f4
算法思路一：集合set + 遍历
解题思路：
根据题意，此 55 张牌是顺子的 充分条件 如下：
除大小王外，所有牌 无重复 ；
设此 55 张牌中最大的牌为 max ，最小的牌为 min （大小王除外），则需满足
除大小王外，所有牌 无重复 ；
设此 55 张牌中最大的牌为 max ，最小的牌为 min （大小王除外），则需满足
max - min < 5
算法：
1、遍历五张牌，遇到大小王（即 0 ）直接跳过。
2、判别重复： 利用 Set 实现遍历判重， Set 的查找方法的时间复杂度为 O(1) ；
3、获取最大 / 最小的牌： 借助辅助变量 ma 和 mi ，遍历统计即可。
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 为大小王的数量。
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)大小额外空间
查看2道真题和解析
