Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में ऐरे साइज को आधा करना


मान लीजिए हमारे पास एक ऐरे arr है। हम इंटीजर्स का एक सेट चुन सकते हैं और ऐरे में इन इंटीजर्स के सभी ऑकरेंसेज को हटा सकते हैं। हमें सेट का न्यूनतम आकार ढूंढना है ताकि ऐरे के कम से कम आधे इंटीजर्स हटा दिए जाएं। उदाहरण के लिए, अगर arr = [3,3,3,3,5,5,5,2,2,7], तो आउटपुट 2 होगा। ऐसा इसलिए क्योंकि अगर हम {3,7} चुनते हैं तो नया ऐरे [5,5,5,2,2] बनेगा जिसका साइज 5 है (यह पुराने ऐरे के साइज के आधे के बराबर है)। साइज 2 के संभावित सेट्स हैं {3,5},{3,2},{5,2}। सेट {2,7} चुनना संभव नहीं है क्योंकि यह नया ऐरे [3,3,3,3,5,5,5] बनाएगा जिसका साइज पुराने ऐरे के आधे से अधिक है।

इसे हल करने के लिए, हम इन स्टेप्स को फॉलो करेंगे:

  • एक मैप m डिफाइन करें, n := arr का साइज, arr में मौजूद प्रत्येक एलिमेंट की फ्रीक्वेंसी को मैप m में स्टोर करें

  • temp नाम का एक ऐरे डिफाइन करें, sz := n, और ret := 0

  • m में प्रत्येक की-वैल्यू पेयर it के लिए:

    • it के वैल्यू को temp में इंसर्ट करें

  • temp ऐरे को सॉर्ट करें

  • i को 0 से temp के साइज तक लूप करें:

    • अगर sz <= n / 2, तो लूप से ब्रेक करें

    • ret को 1 से बढ़ाएं

    • sz को temp[i] से घटाएं

  • ret लौटाएं

उदाहरण (C++)

बेहतर समझ के लिए निम्न इम्प्लीमेंटेशन देखें:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int minSetSize(vector<int>& arr) {
        unordered_map <int, int> m;
        int n = arr.size();
        for(int i = 0; i < n; i++){
            m[arr[i]]++;
        }
        vector <int> temp;
        unordered_map <int, int> :: iterator it = m.begin();
        int sz = n;
        int ret = 0;
        while(it != m.end()){
            temp.push_back(it->second);
            it++;
        }
        sort(temp.rbegin(), temp.rend());
        for(int i = 0; i < temp.size(); i++){
            if(sz <= n / 2)break;
            ret++;
            sz -= temp[i];
        }
        return ret;
    }
};

int main(){
    vector<int> v = {3,3,3,3,5,5,5,2,2,7};
    Solution ob;
    cout << (ob.minSetSize(v));
}

इनपुट

[3,3,3,3,5,5,5,2,2,7]

आउटपुट

2

  1. इमेज फ़ाइल का आकार कैसे कम करें इमेज फ़ाइल का आकार कैसे कम करें

    पहले, मैंने एक्सप्लोरर में बिल्ट-इन ईमेल विकल्प का उपयोग करके या Image Resizer for Windows नामक डेस्कटॉप प्रोग्राम का उपयोग करके इमेज फ़ाइल का आकार कम करने पर एक लेख लिखा था। ये अच्छे विकल्प हैं, लेकिन इमेज को ऑप्टिमाइज़ करने के कई अन्य तरीके हैं। साथ ही, बहुत सी वेबसाइटें आपको Paint का उपयोग करने क

  1. C++ में भूलभुलैया समस्या का समाधान C++ में भूलभुलैया समस्या का समाधान

    समस्या विवरण मान लीजिए एक गेंद एक भूलभुलैया में है जिसमें खाली स्थान और दीवारें हैं। गेंद किसी भी दिशा में (ऊपर, नीचे, बाएं, दाएं) लुढ़ककर खाली रास्तों से गुजर सकती है, लेकिन यह तब तक नहीं रुकेगी जब तक यह दीवार से न टकरा जाए। जब गेंद रुकती है, तो यह अगली दिशा चुन सकती है। हमें गेंद की प्रारंभिक स्

  1. - C++ में ऐरे डेके (Array Decay) क्या है?

    ऐरे डेके क्या है? ऐरे के प्रकार और आयामों की हानि को ऐरे डेके कहते हैं। यह तब होता है जब ऐरे को फ़ंक्शन में पॉइंटर या मान द्वारा पास किया जाता है। पहला पता पॉइंटर के रूप में भेजा जाता है, इसलिए ऐरे का आकार मूल नहीं रहता। C++ प्रोग्राम उदाहरण #include <iostream> using namespace std; void Dis