Divide Array in Sets of K Consecutive Numbers แบ่งอาร์เรย์เป็นชุด K ตัวติดกันใน C++

ให้อาร์เรย์ nums และ k หาว่าแบ่งเป็นชุดๆ ละ k ตัวที่เป็นจำนวนติดกันได้ไหม

ตัวอย่าง: [1,2,3,3,4,4,5,6], k=4 → true ([1,2,3,4] และ [3,4,5,6])

วิธีแก้ปัญหา (Greedy + Frequency Map)

1. นับความถี่ใน map m
2. เรียง nums
3. วนทุก x ใน nums:
   • ถ้า m[x-1] = 0 และ m[x] > 0 (x เป็นต้นของชุดใหม่):
     • พยายามสร้างชุด x, x+1, ..., x+k-1
     • ถ้าตัวไหนขาด → false
     • ลดความถี่แต่ละตัว
4. ถ้าใช้หมดทุกตัว → true

ตัวอย่างโค้ด C++

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

class Solution {
public:
    bool isPossibleDivide(vector<int>& nums, int k) {
        map<int, int> m;
        int n = nums.size();
        for (int x : nums) m[x]++;
        int cnt = 0;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            if (m[x - 1] == 0 && m[x] > 0) {
                int l = k;
                while (k > 0) {
                    if (m[x] > 0) { m[x]--; }
                    else return false;
                    x++; cnt++; k--;
                }
                k = l;
            }
        }
        return cnt == n;
    }
};

int main() {
    vector<int> v = {1,2,3,3,4,4,5,6};
    Solution ob;
    cout << ob.isPossibleDivide(v, 4);
    return 0;
}

Input

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

Output

1