Giảm Kích Thước Mảng Đi Một Nửa Trong C++

Giả sử mảng arr. Chúng ta chọn một tập hợp các số nguyên và xóa tất cả các lần xuất hiện của các số này trong mảng. Tìm kích thước tối thiểu của tập hợp sao cho ít nhất một nửa số lượng phần tử của mảng bị xóa.

Ví dụ: arr = [3,3,3,3,5,5,5,2,2,7] → 2. Chọn {3,7} mảng mới [5,5,5,2,2] kích thước 5 (bằng một nửa). Các tập hợp kích thước 2 có thể: {3,5}, {3,2}, {5,2}. {2,7} không được vì mảng mới kích thước > n/2.

Để giải quyết, chúng ta làm theo các bước:

• Định nghĩa map m, n = arr.size(), lưu tần suất từng phần tử vào m.

• Tạo mảng temp, sz = n, ret = 0.

• Với mỗi cặp trong m: push giá trị vào temp.

• Sắp xếp temp giảm dần.

• Với i từ 0 đến temp.size()-1: nếu sz <= n/2 break; ret++; sz -= temp[i].

• Trả về ret.

Ví dụ (C++)

Hãy xem triển khai sau để hiểu rõ hơn:

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

class Solution {
public:
    int minSetSize(vector<int>& arr) {
        unordered_map <int, int> m;
        int n = arr.size();
        for(int i = 0; i < n; i++){
            m[arr[i]]++;
        }
        vector <int> temp;
        unordered_map <int, int> :: iterator it = m.begin();
        int sz = n;
        int ret = 0;
        while(it != m.end()){
            temp.push_back(it->second);
            it++;
        }
        sort(temp.rbegin(), temp.rend());
        for(int i = 0; i < temp.size(); i++){
            if(sz <= n / 2) break;
            ret++;
            sz -= temp[i];
        }
        return ret;
    }
};

int main(){
    vector<int> v = {3,3,3,3,5,5,5,2,2,7};
    Solution ob;
    cout << (ob.minSetSize(v));
}

Đầu vào

[3,3,3,3,5,5,5,2,2,7]

Đầu ra

2