अ‍ॅरेमध्ये सर्व घटक समान करण्यासाठी किमान ऑपरेशन


अडचण पातळी सोपे
वारंवार विचारले ऍमेझॉन काळा दगड किल्ला डायरेक्टि फ्लिपकार्ट खरंच यांडेक्स
अरे हॅशिंग

“अ‍ॅरेमध्ये सर्व घटक समान करण्यासाठी किमान ऑपरेशन” ही समस्या नमूद करते की आपल्याला एक दिले गेले आहे अॅरे काही सोबत पूर्णांक त्यात. अ‍ॅरे बरोबरी करण्यासाठी केल्या जाणा the्या किमान ऑपरेशन्स आपल्याला शोधाव्या लागतील.

उदाहरण

अ‍ॅरेमध्ये सर्व घटक समान करण्यासाठी किमान ऑपरेशन

[ 1,3,2,4,1]
3

स्पष्टीकरण

एकतर 3 वजाबाकी करता येतात किंवा समान अ‍ॅरे करण्यासाठी 3 जोडणे करता येते.

[5,3,2,4,1]
4

स्पष्टीकरण

एकतर 4 वजाबाकी करता येतात किंवा समान अ‍ॅरे करण्यासाठी 4 जोडणे करता येते.

सर्व घटक समान करण्यासाठी किमान ऑपरेशन्स शोधण्यासाठी अल्गोरिदम

  1. घोषित ए नकाशा.
  2. मी <एन असताना, लूप चालू आहे
    1. अ‍ॅरे घटक आणि प्रत्येक घटकाची वारंवारता नकाशामध्ये संचयित करा.
  3. सेट करा “मॅक्सकउंट” 0 पर्यंत.
  4. पळवाट तपासून पहा “मॅक्सकउंट” नकाशामधील की च्या मूल्यापेक्षा कमी आहे
    1. जर अट पूर्ण होईल तर सेट करा “मॅक्सकउंट” की च्या मूल्यापर्यंत.
  5. परतावा (एन - “कमाल खाते”).

स्पष्टीकरण

आमच्याकडे एक आहे पूर्णांक अॅरे इनपुट म्हणून अ‍ॅरे समान करण्यासाठी करता येणारी किमान कार्ये शोधणे हे आपले कार्य आहे. आम्ही त्यात एक नकाशा वापरणार आहोत. नकाशा वापरुन, आम्ही घटकांना त्यांच्या वारंवारतेसह सहजपणे संग्रहित करू शकतो, कारण ऑपरेशन्स शोधण्यासाठी फ्रिक्वेन्सी महत्त्वपूर्ण भूमिका बजावते.

आम्ही जास्तीत जास्त वारंवारतेसह घटक शोधणार आहोत आणि आम्ही अ‍ॅरेची लांबी आणि जास्तीत जास्त वारंवारता मोजणीमधील फरक परत करतो कारण आपल्याकडे आधीपासूनच एरेमध्ये घटक आहे जो पुनरावृत्ती झाला आहे म्हणून सर्व घटक एकसारखे बनवण्यासाठी कमी ऑपरेशन्स घेतात. कारण हे विशिष्ट बदलण्याऐवजी आहे आणि म्हणूनच (अ‍ॅरेची लांबी- जास्तीत जास्त वारंवारता) ते येथे कार्य करते.

आपण येथे एका उदाहरणाचा विचार करूया:

उदाहरण

अरे: {1, 5, 2, 1, 3, 2, 1};

पहिल्या सर्वात घटकापासून प्रारंभ करून, आम्ही संपूर्ण अ‍ॅरेला मागे टाकतो आणि प्रत्येक घटकाची वारंवारता मोजतो आणि त्यास नकाशावर संचयित करतो.

i = 0,

अरे [i] = 1

countFreq = [1: 1]

i = 1

अरे [i] = 5

countFreq = [1: 1,5: 1]

i = 2

अरे [i] = 2

countFreq = [1: 1,5: 1,2: 1]

i = 3

अरे [i] = 1

countFreq = [1: 2,5: 1,2: 1] => येथे आपल्याला दोनदा “1” घटक सापडतील जेणेकरून 1 ची वारंवारता संख्या वाढेल.

i = 4

अरे [i] = 3

countFreq=[1:2,5:1,2:1,3:1]

i = 5

अरे [i] = 2

countFreq = [१: २,1: १,२: २::: १] => येथे आपल्याला दोनदा “2,5” घटक सापडतील जेणेकरून 1,2 ची वारंवारता संख्या वाढेल.

i = 6

अरे [i] = 1

countFreq = [१: 1: १,२: २::: १] => येथे आपल्याला तीनदा “१” घटक आढळेल जेणेकरून 3,5 ची वारंवारता संख्या वाढेल.

आता प्रारंभ करा “मॅक्सकउंट” ते ०. आणि प्रत्येक वारंवारतेपेक्षा जास्त असल्यास ते तपासा “मॅक्सकउंट”, जास्त असल्याचे आढळल्यास त्या वारंवारतेचे मूल्य संचयित करा “मॅक्सकउंट”

शेवटी, आपल्यात सर्वात मोठी वारंवारता असेल “मॅक्सकउंट”.

आम्ही एन- परत “मॅक्सकउंट” => 7-3 = 4, म्हणजे अ‍ॅरे समान करण्यासाठी आपण कमीतकमी 4 ऑपरेशन्स केल्या पाहिजेत.

कोड

अ‍ॅरेमध्ये सर्व घटक समान करण्यासाठी किमान ऑपरेशन शोधण्यासाठी सी ++

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

int getMinimumOperation (int arr[], int n)
{
  unordered_map<int, int> countFreq;
  for (int i=0; i<n; i++)
    countFreq[arr[i]]++;

  int maxCount = 0;
  for (auto i : countFreq)
    if (maxCount < i.second)
      maxCount = i.second;

  return (n - maxCount);
}
int main()
{
  int arr[] = {1, 5, 2, 1, 3, 2, 1};
  int n = sizeof(arr) / sizeof(arr[0]);
  cout << getMinimumOperation(arr, n);
  return 0;
}
4

अ‍ॅरेमध्ये सर्व घटक समान करण्यासाठी किमान ऑपरेशन शोधण्यासाठी जावा कोड

import java.util.*;
class minimumOperations
{
    public static int getMinimumOperations(int arr[], int n)
    {
        HashMap<Integer, Integer> countFreq = new HashMap<Integer, Integer>();

        for (int i=0; i<n; i++)
        {
            if(countFreq.containsKey(arr[i]))
            {
                countFreq.put(arr[i], countFreq.get(arr[i])+1);
            }
            else
            {
                countFreq.put(arr[i], 1);
            }
        }
        int maxCount = 0;

        Set<Integer> s = countFreq.keySet();

        for (int i : s)
            if (maxCount < countFreq.get(i))
                maxCount = countFreq.get(i);


        return (n - maxCount);
    }
    public static void main(String[] args)
    {
        int arr[] = {1, 5, 2, 1, 3, 2, 1};
        int n = arr.length;
        System.out.println(getMinimumOperations(arr, n));
    }
}
4

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

O (n) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या.

स्पेस कॉम्प्लेक्सिटी

O (n) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या.