सी ++ में सरणी के सभी तत्वों को समान बनाने के लिए न्यूनतम डिलीट ऑपरेशंस।

समस्या कथन

n तत्वों की एक सरणी को देखते हुए जैसे कि तत्व दोहरा सकते हैं। हम सरणी से किसी भी संख्या में तत्वों को हटा सकते हैं। कार्य इसे समान बनाने के लिए सरणी से हटाए जाने वाले तत्वों की न्यूनतम संख्या को खोजना है।

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

सभी सरणी तत्वों को समान बनाने के लिए हमें हाइलाइट किए गए 5 तत्वों को हटाना होगा।

एल्गोरिदम

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

उदाहरण

#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;
}

आउटपुट

जब आप उपरोक्त प्रोग्राम को संकलित और निष्पादित करते हैं। यह निम्न आउटपुट उत्पन्न करता है -

Required deletes: 5