Tuyên bố vấn đề
Cho một mảng gồm n phần tử sao cho các phần tử có thể lặp lại. Chúng ta có thể xóa bất kỳ số phần tử nào khỏi mảng. Nhiệm vụ là tìm số phần tử tối thiểu bị xóa khỏi mảng để làm cho nó bằng nhau.
arr[] = {10, 8, 10, 7, 10, -1, -4, 12} Chúng ta phải xóa 5 phần tử được đánh dấu để làm cho tất cả các phần tử của mảng giống nhau.
Thuật toán
1. Count frequency of each element 2. Find maximum frequecy among the frequencies. Let us call this as maxFrequncy 3. Elements to be deleted: n – maxFrequecy where n is size of an array
Ví dụ
#include <iostream>
#include <unordered_map>
#include <climits>
#define SIZE(arr) (sizeof(arr)/sizeof(arr[0]))
using namespace std;
int minDeleteOperations(int *arr, int n){
unordered_map<int, int> frequecy;
int maxFrequency = INT_MIN;
for (int i = 0; i < n; ++i) {
frequecy[arr[i]]++;
}
for (auto it = frequecy.begin(); it != frequecy.end(); ++it) {
maxFrequency = max(maxFrequency, it->second);
}
return (n - maxFrequency);
}
int main(){
int arr[] = {10, 8, 10, 7, 10, -1, 9, 4};
cout << "Required deletes: " << minDeleteOperations(arr, SIZE(arr)) << "\n";
return 0;
} Đầu ra
Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -
Required deletes: 5