846. Hand of Straights.md

846. Hand of Straights

思路

这道题说手里有扑克牌若干，是否能将手里的牌都以顺子的形式出完，每组顺子的牌数都为W。

由于顺子是等差为1的等差数列，所以如果知道了最小元素也就知道了其他所有元素。所以我们可以使用贪婪的算法：首先取出手中最小的牌，再按照不断+1的规则组成第一组顺子；再在剩下的牌中按照上一次一样的规则组成第二组顺子；以此类推。由此可见，我们需要一个快速获得最小值和快速删除元素的数据结构，map和multiset满足我们的要求。

若使用map，我们可以记录元素值到出现次数的隐射，删除操作即将出现次数减1；若使用multiset，我们每次根据迭代器删除元素即可，即.erase(.find(val))（不能根据元素值删除.erase(val)，那样会将所有值相等的元素都删了），代码中我们使用multiset。

时间复杂度O(nlogn)，空间复杂度O(n)

C++

class Solution {
public:
    bool isNStraightHand(vector<int>& hand, int W) {
        int n = hand.size(), groups = n / W;
        if(n % W) return false;
        
        multiset<int>cards;
        for(int num: hand) cards.insert(num);
        
        int pre;
        while(groups--){
            pre = *cards.begin(); 
            cards.erase(cards.begin());
            for(int j = 1; j < W; j++){
                if(cards.find(++pre) == cards.end()) return false;
                cards.erase(cards.find(pre));
            }
        }
        return true;
    }
};