🔗 🟡 1296. Divide Array in Sets of K Consecutive Numbers 1490

tags: `Weekly Contest 168` `貪心(Greedy)` `雜湊表(Hash Table)` `排序(Sorting)`

題意

給定一個整數陣列 $nums$ 和一個正整數 $k$ ，檢查是否可以將此陣列分成 $k$ 個連續數字的集合。

如果可以，返回 $\rm{True}$ 。否則，返回 $\rm{False}$ 。

約束條件

$1 \leq k \leq nums.length \leq 10^5$
$1 \leq nums[i] \leq 10^9$

思路：貪心(Greedy) + 雜湊表(Hash Table) + 排序(Sorting)

基於貪心思路，由於我們需要讓每組集合都是 $k$ 個連續的數字，因此 $nums$ 中的最小數字必定是一組集合的起點。假設陣列中最小的數字為 $x$ ，則我們需要將 $x, x+1, x+2, ..., x+k-1$ 這 $k$ 個數字分到同一組集合中。

因此我們可以使用一個雜湊表(Hash Table) $cnt$ 來記錄每個數字的數量，並且對其鍵值進行排序（或是使用 C++ 的 map）來確保我們能夠從最小的數字開始檢查連續性。

具體步驟如下：

使用 Counter 或 map 來統計每個數字的數量，並依照鍵值排序。
遍歷排序後的鍵值，對每個數字進行檢查，如果該個數字的數量為 $0$ ，則跳過。否則則嘗試組成以這個數字為起點的連續組合，共需要組成 $cnt[k]$ 組連續數字的集合。
如果某個數字無法組成連續組合（即該組內的某個數字的剩餘數量小於需要的數量），則返回 $\rm{False}$ 。
每次成功組成一個連續數字的集合後，減少相應數字的數量。
如果所有數字都能成功組成連續數字的集合，則返回 $\rm{True}$ 。

複雜度分析

時間複雜度： $\mathcal{O}(n \log n)$ $O (n lo g n)$ ，其中 $n$ $n$ 為陣列的長度。
- 統計每個數字的出現次數需要 $\mathcal{O}(n)$ 時間。
- 排序需要 $\mathcal{O}(m \log m)$ 時間，其中 $m$ 為不同數字的個數，可以視為 $\mathcal{O}(n)$ 。
- 每個數字最多會被遍歷一次，因此處理所有數字的過程需要 $\mathcal{O}(m + n)$ 時間，可以視為 $\mathcal{O}(n)$ 。
空間複雜度： $\mathcal{O}(n)$ ，忽略排序的空間複雜度。

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        cnt = Counter(nums)
        for x in sorted(cnt.keys()):
            if cnt[x] == 0:
                continue
            need = cnt[x]
            for i in range(k):
                if cnt[x+i] < need:
                    return False
                cnt[x+i] -= need
        return True

class Solution {
public:
    bool isPossibleDivide(vector<int>& nums, int k) {
        map<int, int> cnt; // ordered map
        for (int x : nums) cnt[x]++;
        for (auto it = cnt.begin(); it != cnt.end(); it++) {
            if (it->second == 0) continue;
            int need = it->second;
            for (int i = 0; i < k; i++) {
                if (cnt[it->first + i] < need) return false;
                cnt[it->first + i] -= need;
            }
        }
        return true;
    }
};