Chia mảng thành các tập K số liên tiếp (Divide Array in Sets of K Consecutive Numbers) trong C++

Cho mảng nums và k. Kiểm tra có thể chia thành các tập con kích thước k gồm các số liên tiếp không.

Ví dụ: [1,2,3,3,4,4,5,6], k=4 → true ([1,2,3,4] và [3,4,5,6]).

Thuật toán (Hash Map + Tham lam)

1. Đếm tần suất mỗi số.
2. Sắp xếp mảng.
3. Duyệt số x từ nhỏ đến lớn. Nếu đã hết và x còn → bắt đầu dãy mới từ x dài k.
4. Trừ tần suất x, x+1, ..., x+k-1. Nếu thiếu → false.

Mã nguồn C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool isPossibleDivide(vector& nums, int k) {
        map freq;
        for (int x : nums) freq[x]++;
        sort(nums.begin(), nums.end());
        for (int x : nums) {
            if (freq[x] == 0) continue;
            for (int i=0; i v = {1,2,3,3,4,4,5,6};
    Solution ob;
    cout << ob.isPossibleDivide(v, 4); // 1 (true)
    return 0;
}

Đầu vào / Đầu ra

Input: [1,2,3,3,4,4,5,6] 4

Output: 1