Problem statement
ให้อาร์เรย์ n องค์ประกอบ อาจมีค่าซ้ำ เราสามารถลบสมาชิกได้จำนวนใดก็ได้ งานคือหาจำนวนสมาชิกน้อยที่สุดที่ต้องลบเพื่อให้อาร์เรย์เหลือค่าเดียวกันทั้งหมด
arr[] = {10, 8, 10, 7, 10, -1, -4, 12}เราต้องลบสมาชิกที่ไฮไลท์ 5 ตัว เพื่อให้อาร์เรย์เหลือค่าเดียวกัน
อัลกอริทึม
1. นับความถี่ของแต่ละองค์ประกอบ 2. หาความถี่สูงสุด เรียกว่า maxFrequency 3. จำนวนที่ต้องลบ: n – maxFrequency โดย n คือขนาดอาร์เรย์
ตัวอย่าง
#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; }ผลลัพธ์
When you compile and execute the above program. It generates the following output −
Required deletes: 5
