javascript - 检查数组JS中的序列

Question

我正在解决 LeetCode 中的一个“简单”问题，名为 Divide Array in Sets of K Consecutive Numbers ，但找不到如何检查序列的方法。从我的 Angular 来看，这将是很多循环:

const isPossibleDivide = (nums, k) => {
    const sorted = nums.sort((a, b) => a - b)
    const counts = {}
    sorted.forEach(item => counts[item] = (counts[item] || 0) + 1)

    // the problem part
    Object.entries(counts).map(([key, value]) => {
        if (value !== 0) {
            counts[key] = value - 1
        }
    })
    console.log(counts)
}

isPossibleDivide([3, 2, 1, 2, 3, 4, 3, 4, 5, 9, 10, 11], 3)

Answer 1

对于这个问题，我们会使用 map 。这将通过:

const isPossibleDivide = (nums, k) => {
    if (!nums.length % k) {
        return false;
    }

    const headsMap = new Map();

    for (const num of nums) {
        headsMap.set(num, headsMap.has(num) ? -~headsMap.get(num) : 1);
    }

    for (let head of nums) {
        if (headsMap.get(head) === 0) {
            continue;
        }

        while (headsMap.get(--head) > 0);
        ++head;
        const count = headsMap.get(head);
        for (let index = 1; index < k; ++index) {
            const curr = headsMap.get(head + index)
            if (curr === undefined || curr < count) {
                return false;
            }

            headsMap.set(head + index, curr - count);
        }

        headsMap.set(head, 0);
    }

    return true;
};

如果我们能够使用双端队列，这个 python 版本会有所帮助:

from typing import List

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int):
        count_map = collections.Counter(nums)
        heads_map = collections.deque()
        last_checked = -1
        opened = 0

        for key in sorted(count_map):
            if opened > count_map[key] or opened > 0 and key > -~last_checked:
                return False
            heads_map.append(count_map[key] - opened)
            last_checked = key
            opened = count_map[key]

            if len(heads_map) == k:
                opened -= heads_map.popleft()

        return opened == 0

在Java中，我们可以使用TreeMap和LinkedList:

public class Solution {
    public static final boolean isPossibleDivide(int[] nums, int k) {
        Map<Integer, Integer> countMap = new TreeMap<>();

        for (int num : nums) {
            countMap.put(num, -~countMap.getOrDefault(num, 0));
        }

        Queue<Integer> headsMap = new LinkedList<>();

        int lastChecked = -1;
        int opened = 0;

        for (int key : countMap.keySet()) {
            if (opened > 0 && key > -~lastChecked || opened > countMap.get(key)) {
                return false;
            }

            headsMap.add(countMap.get(key) - opened);
            lastChecked = key;
            opened = countMap.get(key);

            if (headsMap.size() == k) {
                opened -= headsMap.remove();
            }
        }

        return opened == 0;
    }
}

---

引用文献

• 有关更多详细信息，您可以参阅 Discussion Board 。有很多可接受的解决方案，具有各种 languages和解释，高效的算法，以及渐近time/space复杂性分析 ^{1 , 2} 在那里。