微信公众号：路人zhang
扫码关注微信公众号

回复“面试手册”，获取本站PDF版

回复“简历”，获取高质量简历模板

回复“加群”，加入程序员交流群

回复“电子书”，获取程序员类电子书

当前位置： 算法 > 剑指offer > 剑指offer 61. 扑克牌中的顺子

剑指offer 61. 扑克牌中的顺子

题目描述

从 若干副扑克牌 中随机抽 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] .

题解

(模拟,排序) O(nlogn)

  1. 先将数组排序
  2. 把 0 先过滤掉，找到第一个不为 0 的位置 k
  3. 遍历数组，如果有重复元素，肯定不能构成顺子
  4. 如果最后一个元素和第一个非 0 元素之差大于 4 nums.back() - nums[k] + 1 > 5 不能构成顺子，否则就是顺子

时间复杂度

数组排序的时间复杂度为 O(nlogn)

空间复杂度

O(1)

C++ 代码

class Solution {
public:
    bool isStraight(vector<int>& nums) {
        if (nums.empty()) return false;
        sort(nums.begin(), nums.end());

        int k = 0;
        while (!nums[k]) k ++ ;

        for (int i = k + 1; i < nums.size(); i ++ )
            if (nums[i - 1] == nums[i])
                return false;
        return nums.back() - nums[k] < 5;
    }
};

Java 代码

import java.util.Arrays;

class Solution {
    public boolean isStraight(int[] nums) {
        if (nums == null || nums.length == 0) {
            return false;
        }

        Arrays.sort(nums);
        int k = 0;
        while (nums[k] == 0) {
            k ++ ;
        }

        for (int i = k + 1; i < nums.length; i ++ ) {
            if (nums[i - 1] == nums[i]) {
                return false;
            }
        }

        return nums[nums.length - 1] - nums[k] < 5;
    }
}

Python 代码

class Solution:
    def isStraight(self, nums: List[int]) -> bool:
        if not nums:
            return False
        
        nums.sort()
        k = 0
        while not nums[k]:
            k += 1
        
        for i in range(k + 1, len(nums)):
            if nums[i - 1] == nums[i]:
                return False
        
        return nums[-1] - nums[k] < 5

本文由读者提供，Github地址：https://github.com/tonngw

点击面试手册，获取本站面试手册PDF完整版

剑指offer