846 Hand of Straights

846. Hand of Straights

1. Question

Alice has ahandof cards, given as an array of integers.

Now she wants to rearrange the cards into groups so that each group is sizeW, and consists ofWconsecutive cards.

Returntrueif and only if she can.

Example 1:

Input: 
hand = [1,2,3,6,2,3,4,7,8], W = 3

Output: 
true

Explanation: 
Alice's hand can be rearranged as [1,2,3],[2,3,4],[6,7,8].

Example 2:

Input: hand = [1,2,3,4,5], W = 4

Output: false

Explanation:
Alice's hand can't be rearranged into groups of 4.

Note:

1. 1 <= hand.length <= 10000

2. 0 <= hand[i] <= 10^9

3. 1 <= W <= hand.length

2. Implementation

(1) Bucket Sort

思路: Bucket Sort的思路并不是很懂

class Solution {
    public boolean isNStraightHand(int[] hand, int W) {
        if (W == 1) return true;

        if (hand.length % W != 0) return false;

        int n = hand.length;
        int H = n / W;

        int[][] buckets = new int[W][H];
        int[] bucketSize = new int[W];

        // each column is a bucket
        for (int card : hand) {
            // use card % W to find the position of card in the bucket
            int indexInBucket = card % W;
            int bucketId = bucketSize[indexInBucket]++;

            if (bucketId >= H) {
                return false;
            }
            buckets[indexInBucket][bucketId] = card;
        }

        for (int i = 0; i < W; i++) {
            Arrays.sort(buckets[i]);
        }

        for (int j = 0; j < H; j++) {
            for (int i = 1; i < W; i++) {
                int pre = buckets[i - 1][j];
                int cur = buckets[i][j];

                if (pre + 1 != cur && pre - cur != W - 1) return false;
            }
        }
        return true;
    }
}

(2) TreeMap

思路: 将card放在TreeMap中，key是card的值，value是card的个数。然后我们从最小的card开始，遍历card到card + W， 如果其中有张card不在map里，说明不能形成一个size为W的straight，return false.否则，更新card在map中的数量

class Solution {
    public boolean isNStraightHand(int[] hand, int W) {
        if (W == 1) return true;

        if (hand.length % W != 0) return false;

        TreeMap<Integer, Integer> map = new TreeMap();

        for (int card : hand) {
            map.put(card, map.getOrDefault(card, 0) + 1);
        }

        while (!map.isEmpty()) {
            int firstCard = map.firstKey();

            for (int card = firstCard; card < firstCard + W; card++) {
                if (!map.containsKey(card)) {
                    return false;
                }
                else {
                    int count = map.get(card);

                    if (count == 1) {
                        map.remove(card);
                    }
                    else {
                        map.put(card, map.get(card) - 1);
                    }
                }
            }
        }
        return true;
    }
}

3. Time & Space Complexity

Bucket Sort:时间复杂度O(), 空间复杂度O()

TreeMap: 时间复杂度O(WlogN), N为card的数量, W是straight的size, 空间复杂度O(N)