846. Single-hander: Data structure simulation

Topic describes

This is 846 on LeetCode. A straight shot, medium difficulty.

Tag: “simulation”, “priority queue”, “hash table”

Alice has a deck of cards in her hand, and she wants to rearrange these cards into groups so that the number of cards in each group is groupSize and consists of consecutive cards of groupSize.

Give you an integer array hand where hand[I] is written on the ith card, and an integer groupSize.

Returns true if she can rearrange the cards; Otherwise, return false.

Example 1:

Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3 output: true explanation: Alice's cards can be rearranged into [1,2,3], [2,3,4], [6,7,8].Copy the code

Example 2:

Input: hand = [1,2,3,4,5], groupSize = 4 output: false explanation: Alice's cards cannot be rearranged into groups of size 4.Copy the code

Tip:

• 
  $1 <= hand.length <= 10^4$
• 
  $0 <= hand[i] <= 10^9$
• 
  $1 <= groupSize <= hand.length$

Emulation + Hash table + Priority queue (heap)

For convenience, let’s call m=groupSizem =groupSize =groupSize.

They’re asking us to divide handhandhand into sections of mm.

In a given
$hand$In the case of, the partition is uniquely determined, so it is essentially a “simulation” process.

Specifically, we can use “hash table” to calculate the “occurrence times” of the values in Handhandhand, and use it to maintain the occurrence times of the remaining elements in real time.

Then maintain (small root heap) all hand[I]hand[I]hand[I] using priority queues. Take the top element TTT from the priority queue (heap) every time to try to be the initiation point/first element of the “sequence” (of course, TTT can be used as the initiation point on the premise that TTT is still a residual element, that is, the occurrence times of real-time maintenance is not 000), and then use TTT as the initiation point/first element to construct the sequence. That [t, t + 1,…, t + m – 1] [t, t + 1,…, t + m – 1] [t, t + 1,…, t + m – 1) elements – occurrences of 1-1-1.

Return True if the number of remaining elements is insufficient to −1-1−1, there is no conflict during construction, otherwise return False.

Code:

class Solution {
    public boolean isNStraightHand(int[] hand, int m) {
        Map<Integer, Integer> map = new HashMap<>();
        PriorityQueue<Integer> q = new PriorityQueue<>((a,b)->a-b);
        for (int i : hand) {
            map.put(i, map.getOrDefault(i, 0) + 1);
            q.add(i);
        }
        while(! q.isEmpty()) {int t = q.poll();
            if (map.get(t) == 0) continue;
            for (int i = 0; i < m; i++) {
                int cnt = map.getOrDefault(t + i, 0);
                if (cnt == 0) return false;
                map.put(t + i, cnt - 1); }}return true; }}Copy the code

• Time complexity: let
  $n$As an arrayhandLength. The complexity of using hash table to perform statistics is
  $O(n)$; The complexity of loading and removing all elements from the heap is zero
  $O(n\log{n})$. The overall complexity is
  $O(n\log{n})$
• Space complexity: O(n)O(n)O(n)

The last

This is the No.846 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics in LeetCode by the start date, some of which have locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.