แบ่งอาร์เรย์เป็นลำดับต่อเนื่องใน C++

ให้อาร์เรย์ nums เรียงจากน้อยไปมาก ต้องการตรวจสอบว่าสามารถแบ่งเป็น 1 หรือหลาย subsequences ได้หรือไม่ โดยแต่ละ subsequence ต้องเป็นจำนวนเต็มต่อเนื่องและมีความยาวอย่างน้อย 3

ตัวอย่าง: [1,2,3,3,4,4,5,5] → true เพราะแบ่งได้เป็น [1,2,3,4,5] และ [3,4,5]

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

1. สร้าง map m เก็บความถี่ของแต่ละตัวเลขใน nums
2. กำหนด cnt = ขนาดของ nums
3. วนลูปทุกตัวเลข x ใน nums:
   • ถ้า m[x], m[x+1], m[x+2] ทั้งหมด > 0:
     • ลด m[x], m[x+1], m[x+2] ลง 1
     • เพิ่ม x ขึ้น 3, ลด cnt ลง 3
     • ขยาย subsequence: while m[x] > 0 และ m[x] > m[x-1]: ลด m[x], เพิ่ม x, ลด cnt
4. คืนค่า true ถ้า cnt = 0 มิฉะนั้น false

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

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

class Solution {
public:
    bool isPossible(vector<int>& nums) {
        unordered_map<int, int> m;
        int n = nums.size();
        for (int i = 0; i < n; i++) m[nums[i]]++;
        int cnt = n;
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            if (m[x] && m[x + 1] && m[x + 2]) {
                m[x]--; m[x + 1]--; m[x + 2]--;
                x += 3; cnt -= 3;
                while (m[x] > 0 && m[x] > m[x - 1]) {
                    cnt--; m[x]--; x++;
                }
            }
        }
        return cnt == 0;
    }
};

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

Input

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

Output

1