समस्या कथन
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> frequency; int maxFrequency = INT_MIN; for (int i = 0; i < n; ++i) { frequency[arr[i]]++; } for (auto it = frequency.begin(); it != frequency.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; }आउटपुट
जब आप उपरोक्त प्रोग्राम को कंपाइल और एक्जीक्यूट करते हैं। यह निम्नलिखित आउटपुट जनरेट करता है -
Required deletes: 5
