Số phép xóa tối thiểu để tất cả phần tử mảng giống nhau trong C++

Đề bài

Cho mảng n phần tử (có thể trùng). Có thể xóa bất kỳ phần tử nào. Tìm số lần xóa tối thiểu để tất cả phần tử còn lại bằng nhau.

arr[] = {10, 8, 10, 7, 10, -1, -4, 12}

Cần xóa 5 phần tử (đã highlight) để các phần tử còn lại đều bằng 10.

Thuật toán

1. Đếm tần suất xuất hiện của mỗi phần tử
2. Tìm tần suất lớn nhất (maxFrequency)
3. Số phần tử cần xóa = n - maxFrequency

Ví dụ mã C++

#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> tanSuat;
    int maxFrequency = INT_MIN;
    for (int i = 0; i < n; ++i) {
        tanSuat[arr[i]]++;
    }
    for (auto it = tanSuat.begin(); it != tanSuat.end(); ++it) {
        maxFrequency = max(maxFrequency, it->second);
    }
    return (n - maxFrequency);
}

int main(){
    int arr[] = {10, 8, 10, 7, 10, -1, 9, 4};
    cout << "Số lần xóa cần: " << minDeleteOperations(arr, SIZE(arr)) << "\n";
    return 0;
}

Kết quả đầu ra

Số lần xóa cần: 5