求:
从扑克牌中随机抽5张牌,判断是不是一个顺子,即这5张牌是不是连续的。2~10为数字本身,A为1,J为11,Q为12,K为13,而大、小王为 0 ,可以看成任意数字。A 不能视为 14。
示例 1:
输入: [1,2,3,4,5]
输出: True
示例 2:
输入: [0,0,1,2,5]
输出: True
限制:
数组长度为 5
数组的数取值为 [0, 13] .
解:
有2种常规做法,不管是哪种做法,注意如果数组中出现了相同的元素,说明有对子,那么肯定无法组成顺子,这种情况在程序里应该有判断。
1、排序后比较
先排序,然后先获取0的数量。(也可以放到一个for循环里统一拿,因为已经排序,最后一位数是不是0不影响结果)
遍历数组,如果相邻元素的差大于1,则考虑使用0进行填补,如果遍历后发现0的个数不足以填补,返回false,否则返回true。
public booleanisStraight(int[] nums) {
intN = nums.length;Arrays.sort(nums);intzeroCount = 0;for(inti = 0;i < N – 1;i++) {
if(nums[i] == 0) ++zeroCount;else if(nums[i] == nums[i + 1]) return false;else if(nums[i + 1] – nums[i] > 1)
zeroCount -= (nums[i + 1] – nums[i] – 1);}
returnzeroCount >= 0;}
时间复杂度 O(Nlog N),N个元素排序复杂度为NlogN
空间复杂度 :O(1)
2、使用HashSet比较
这里没有记录0的个数,而是直接跳过了0。之所以可以这么操作的逻辑是我们发现,不考虑0来遍历数组,如果最大最小值之差小于5(题目要求的张数),则可以形成顺子,否则不能。这里同样需要去重,我们考虑使用Hashset去重,一个元素在遍历时,如果发现hashSet已经有了,说明在之前出现过,返回false。
这个方法的好处是不需要进行排序。
public booleanisStraight(int[] nums) {
intN = nums.length;intmin = 14,max = 0;Set iSet = newHashSet<>();for(inti = 0;i < N;i++) {
if(nums[i] == 0) continue;min = Math.min(min,nums[i]);max = Math.max(max,nums[i]);if(iSet.contains(nums[i])) return false;iSet.add(nums[i]);}
returnmax – min < 5;}