算法思路一:集合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)大小额外空间