846.Hand-of-Straights

846. Hand of Straights

题目地址

https://leetcode.com/problems/hand-of-straights/

题目描述

Alice has a hand of cards, given as an array of integers.

Now she wants to rearrange the cards into groups so that each group is size W, and consists of W consecutive cards.

Return true if 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 <= hand.length <= 10000
0 <= hand[i] <= 10^9
1 <= W <= hand.length

代码

Approach #1 TreeMap to Count Slidewindow

Time: O(N * (N/W)) && Space: O(N)

class Solution {
  public boolean isNStraightHand(int[] hand, int W) {
        TreeMap<Integer, Integer> count = new TreeMap();
    for (int card: hand) {
      if (!count.containsKey(card)) {
        count.put(card, 1);
      } else {
        count.replace(card, count.get(card) + 1);
      }
    }

    while (count.size() > 0) {
      int first = count.firstKey();
      for (int card = first; card < first + W; card++) {
        if (!count.containsKey(card))        return false;
        int c = count.get(card);
        if (c == 1)        {
          count.remove(card);
        } else {
          count.replace(card, c - 1);
        }
      }
    }

    return true;
  }
}