Reduce Array Size to The Half ใน C++ : ลบ Element ให้เหลือ ≤ ครึ่งด้วย Set ขนาดน้อยสุด

ให้ Array arr เลือก **Set of Integers** ลบ **ทุก Occurrence** ของ Integers ใน Set นั้นออกจาก Array ให้ Array เหลือขนาด **≤ n/2** หา **ขนาด Set น้อยที่สุด**

ตัวอย่าง

arr = [3,3,3,3,5,5,5,2,2,7] (n=10, Target ≤ 5)

• Frequency: 3->4, 5->3, 2->2, 7->1
• Greedy: เลือก Freq ใหญ่สุดก่อน: 3 (4) -> เหลือ 6, เลือก 5 (3) -> เหลือ 3 ≤ 5 -> **Size 2**
• Set {3,5} หรือ {3,2} หรือ {5,2} ก็ได้

Output: 2

แนวทาง: Greedy + Frequency Sort

1. Count Frequency ของแต่ละ Number -> Map
2. Extract Frequencies -> Sort **Descending**
3. Iterate Frequencies จากมากไปน้อย:
   • ลบ Frequency นั้นออกจาก remaining
   • ans++
   • ถ้า remaining <= n/2 -> Break

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

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

class Solution {
public:
    int minSetSize(vector<int>& arr) {
        unordered_map<int, int> freq;
        for (int x : arr) freq[x]++;

        vector<int> counts;
        for (auto& [_, c] : freq) counts.push_back(c);

        sort(counts.rbegin(), counts.rend()); // Descending

        int remaining = arr.size();
        int target = remaining / 2;
        int ans = 0;

        for (int c : counts) {
            if (remaining <= target) break;
            remaining -= c;
            ans++;
        }
        return ans;
    }
};

Input / Output

Input:  [3,3,3,3,5,5,5,2,2,7]
Output: 2

ความซับซ้อน (Complexity)

• Time: O(N + M log M) — N=Array Size, M=Unique Numbers (M ≤ N)
• Space: O(M) — Frequency Map + Counts Vector

ทำไม Greedy ถูกต้อง?

เพื่อลดขนาด Array ให้ ≤ Half ด้วย **จำนวน Distinct Values น้อยที่สุด** ควรลบ Values ที่มี **Frequency สูงสุด** ก่อน (แต่ละค่าที่ลบ "คุ้มค่า" มากที่สุด) นี่คือ Greedy Choice Property ที่พิสูจน์ได้ครับ