Giả sử chúng ta có một mảng arr. Chúng ta có thể chọn một tập hợp các số nguyên và loại bỏ tất cả các lần xuất hiện của các số nguyên này trong mảng. Chúng ta phải 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ố nguyên của mảng bị loại bỏ. Vì vậy, ví dụ, nếu arr =[3,3,3,3,5,5,5,2,2,7], thì đầu ra sẽ là 2. Điều này là do nếu chúng ta chọn {3,7}, điều này sẽ làm cho mảng mới [5,5,5,2,2] có kích thước 5 (bằng một nửa kích thước của mảng cũ). Các tập hợp kích thước 2 có thể có là {3,5}, {3,2}, {5,2}. Không thể chọn tập hợp {2,7} vì nó sẽ làm cho mảng mới [3,3,3,3,5,5,5] có kích thước lớn hơn một nửa kích thước của mảng cũ.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định một bản đồ m, n:=kích thước của arr, lưu trữ tần suất của mỗi phần tử hiện diện trong arr vào bản đồ m
-
xác định một mảng được gọi là temp, sz:=n và ret:=0
-
đối với mỗi khóa-giá trị, hãy ghép nối nó bằng m
-
chèn giá trị của nó vào tạm thời
-
-
sắp xếp mảng tạm thời
-
cho tôi trong phạm vi 0 đến kích thước của nhiệt độ
-
nếu sz <=n / 2, thì ngắt khỏi vòng lặp
-
tăng ret lên 1
-
giảm sz theo nhiệt độ [i]
-
-
trả lại ret
Ví dụ (C ++)
Hãy cùng chúng tôi xem cách 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;
}
};
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