扑克牌顺子

题目描述

LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)…他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子…..LL不高兴了,他想了想,决定大\小王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何，如果牌能组成顺子就输出true，否则就输出false。为了方便起见,你可以认为大小王是0。

解答

public boolean isContinuous(int[] numbers) {
    if (numbers == null || numbers.length == 0) {
        return false;
    }
    Arrays.sort(numbers);

    int i = 0;
    for (; i < numbers.length; i++) {
        if (numbers[i] != 0) {
            break;
        }
    }
    for (int j = i + 1; j < numbers.length; j++) {
        if (numbers[j] == numbers[j - 1]) {
            return false;
        }
    }
    int gap = numbers[4] - numbers[i];
    if (gap < 5) {
        return true;
    } else {
        return false;
    }
}

官方题解

链接：https://www.nowcoder.com/questionTerminal/762836f4d43d43ca9deb273b3de8e1f4?answerType=1&f=discussion
来源：牛客网

题目抽象：给定一个长度为5（排除空vector），包含0-13的数组，判断公差是否为1.

方法一：set+遍历

我们分两种情况考虑，
一. 如果vector中不包含0的情况：
那么如何判断呢？因为需要是顺子，所以首先不能有重复值，如果没有重复值，那么形如[1 2 3 4 5]
[5 6 7 8 9]，会发现最大值与最小值的差值应该小于5.

二. 如果vector中包含0：
发现除去0后的值，判断方法和1中是一样的。

所以根据如上两个条件，算法过程如下：

初始化一个set，最大值max_ = 0, 最小值min_ = 14
遍历数组，对于大于0的整数，没有在set中出现，则加入到set中，同时更新max_, min_
如果出现在了set中，直接返回false
数组遍历完，最后再判断一下最大值与最小值的差值是否小于5

代码如下：

class Solution {
public:
    bool IsContinuous( vector<int> numbers ) {
        if (numbers.empty()) return false;
        set<int> st;
        int max_ = 0, min_ = 14;
        for (int val : numbers) {
            if (val > 0) {
                if (st.count(val) > 0) return false;
                st.insert(val);
                max_ = max(max_, val);
                min_ = min(min_, val);
            }
        }
        return max_ - min_ < 5;
    }
};

时间复杂度：O(N)
空间复杂度：O(N)

方法二：排序+遍历

根据方法一的分析，实现上如果不用set判断是否有重复值的话，还可以先排序，然后如果有重复值，那么肯定相邻。
所以代码如下：

class Solution {
public:
    bool IsContinuous( vector<int> numbers ) {
        if (numbers.empty()) return false;
        sort(numbers.begin(), numbers.end());
        int i = 0, sz = numbers.size();
        for (int j=0; j<sz; ++j) {
            if (numbers[j] == 0) {
                ++i; // i 记录最小值的下标
                continue;
            }
            if (j+1<sz && numbers[j] == numbers[j+1]) return false;
        }
        return numbers.back() - numbers[i] < 5;
    }
};

时间复杂度：O(NlogN)
空间复杂度：O(1)