846. 一手顺子

Approach 1

class Solution {
    public boolean isNStraightHand(int[] hand, int groupSize) {
        if (hand.length % groupSize != 0) return false;
        Arrays.sort(hand);
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < hand.length; i++) {
            map.put(hand[i], map.getOrDefault(hand[i], 0) + 1);
        }
        for (int i = 0; i < hand.length; i++) {
            int x = hand[i];
            if (!map.containsKey(x)) {
                continue;
            }

            for (int j = 0; j < groupSize; j++) {
                int num = x + j;
                if (!map.containsKey(num)) {
                    return false;
                }
                Integer cnt = map.get(num);
                if (cnt == 1) {
                    map.remove(num);
                } else {
                    map.put(num, cnt - 1);
                }
            }
        }
        return true;
    }
}

Approach 2

class Solution {
    public boolean isNStraightHand(int[] hand, int groupSize) {
        int n = hand.length;
        if (n % groupSize != 0) return false;
        if (groupSize == 1) return true;
        int index = 0;
        Arrays.sort(hand);
        while (index < n) {
            if (hand[index] == -1) {
                index++;
                continue;
            }
            int pre = index;
            int cur = pre + 1;
            int cnt = groupSize;
            while (cur < n && cnt > 1) {
                if (hand[pre] == hand[cur] || hand[cur] == -1) {
                    cur++;
                    continue;
                }

                if (hand[pre] == -1) {
                    pre++;
                    continue;
                }

                if (hand[pre] != hand[cur] - 1) {
                    return false;
                }

                hand[pre] = -1;
                pre = cur;
                cur++;
                cnt--;
            }
            if (cnt > 1) return false;
            hand[cur-1] = -1;
            index++;
        }
        return true;
    }
}

细节优化后：

class Solution {
    public boolean isNStraightHand(int[] hand, int groupSize) {
        int n = hand.length;
        if (n % groupSize != 0) return false;
        if (groupSize == 1) return true;
        int index = 0;
        Arrays.sort(hand);
        while (index < n) {
            if (hand[index] == -1) {
                index++;
                continue;
            }
            int pre = index;
            int cur = pre + 1;
            int cnt = groupSize;
            while (cur < n && cnt > 1) {
                if (hand[pre] == hand[cur] || hand[cur] == -1) {
                    cur++;
                    continue;
                }

                // 这里可以删掉，左边指针一定会指向非-1的数
                // 因为是从cur指针继承的，而cur一定会遍历到非-1的数
                // if (hand[pre] == -1) {
                //     pre++;
                //     continue;
                // }

                if (hand[pre] != hand[cur] - 1) {
                    return false;
                }

                hand[pre] = -1;
                pre = cur;
                cur++;
                cnt--;
                // 不一定要到外面处理，可以在for循环中判断cnt最后一遍循环的值进行处理。
                if (cnt == 1) hand[cur-1] = -1;
            }
            if (cnt > 1) return false;
            index++;
        }
        return true;
    }
}

approach 3，哈希表+有序列表

class Solution {
    public boolean isNStraightHand(int[] hand, int gs) {
        if (hand.length % gs != 0) return false;
        TreeSet<Integer> ts = new TreeSet<>();
        Map<Integer, Integer> map = new HashMap<>();

        for (int i : hand) {
            int cnt = map.getOrDefault(i, 0);
            map.put(i, cnt + 1);
            if (cnt == 0) ts.add(i);
        }
        while (!ts.isEmpty()) {
            int a = ts.first();
            int aCnt = map.get(a);
            if (--aCnt == 0) ts.remove(a);
            map.put(a, aCnt);
            for (int i = 1; i < gs; i++) {
                int cnt = map.getOrDefault(a + i, 0);
                if (cnt == 0) return false;
                if (--cnt == 0) {
                    ts.remove(a + i);
                }
                map.put(a + i, cnt);
            }
        }
        return ts.isEmpty();
    }
}