सर्वात लहान घटक अचूकपणे के टाइम्स पुनरावृत्ती


अडचण पातळी मध्यम
वारंवार विचारले बेलझाबर कोमली मीडिया नेटस्कोप , NVIDIA ऑपेरा सेवा यूएचजी ऑप्टम
अरे हॅश अक्षरमाळा

आम्हाला आकार n वर अ‍ॅरे [A] दिले आहेत. आम्हाला सर्वात लहान घटक शोधायचा आहे ज्याचा अचूक के वेळा पुनरावृत्ती केला जातो अॅरे.

उदाहरण

इनपुट

अ [] = {1, 2, 2, 5, 5, 2, 5}

के = 3

उत्पादन

फ्रिक्वेन्सी के सह सर्वात लहान घटक म्हणजेः 2

दृष्टीकोन 1: क्रूर शक्ती

मुख्य कल्पना

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

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

  1. असत्य सह व्हेरिएबल 'फ्लॅग' सुरू करा. आम्हाला फ्रिक्वेन्सी के सह काही घटक सापडले किंवा नसले तर ध्वजांकित करा.
  2. मी 0 ते एन -1 श्रेणीतील लूप चालवा
    1. शून्यासह चल गणना प्रारंभ करा जी अ‍ॅरेची वारंवारता गणना करेल [i].
    2. 0 ते एन -1 श्रेणीतील j साठी लूप चालवा
      1. जर ए [जे] ए च्या समान असेल [i], वाढीची गणना १ ने करा.
    3. गणना के के समान असल्यास, उत्तरे अद्यतनित करा = मि (उत्तर, ए [i]).
  3. तपासा, ध्वज सत्य असल्यास उत्तरे मुद्रित करा, अन्यथा मुद्रण करा की वारंवारता के बरोबर कोणतेही घटक नाहीत.

अंमलबजावणी

सी ++ प्रोग्राम

#include <bits/stdc++.h>
using namespace std;
void smallestElementRepeatedExactlyKTimes(vector<int> A, int K)
{
    int n = A.size();
    bool flag = false;
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        int count = 0;
        for (int j = 0; j < n; j++)
        {
            if (A[i] == A[j])
            {
                count++;
            }
        }
        if (count == K)
        {
            if (flag == false)
            {
                flag = true;
                ans = A[i];
            }
            else
            {
                ans = min(ans, A[i]);
            }
        }
    }
    if (flag == false)
    {
        cout << "There is no element with frequency K.";
    }
    else
    {
        cout << "Smallest element with frequency K is: " << ans;
    }
    return;
}
int main()
{
    vector<int> A = {1, 2, 2, 5, 5, 2, 5};
    int K = 3;
    smallestElementRepeatedExactlyKTimes(A, K);
    return 0;
}
Smallest element with frequency K is: 2

जावा कार्यक्रम

public class Main
{
    static void smallestElementRepeatedExactlyKTimes(int A[],int K)
    {
        int n = A.length;
        boolean flag = false;
        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            int count = 0;
            for (int j = 0; j < n; j++)
            {
                if (A[i] == A[j])
                {
                    count++;
                }
            }
            if (count == K)
            {
                if (flag == false)
                {
                    flag = true;
                    ans = A[i];
                }
                else
                {
                    ans = Math.min(ans, A[i]);
                }
            }
        }
        if (flag == false)
        {
            System.out.print("There is no element with frequency K.");
        }
        else
        {
            System.out.print("Smallest element with frequency K is: "+ ans);
        }
        return;
    }
  public static void main(String[] args) {
    int A[] = {1, 2, 2, 5, 5, 2, 5};
        int K = 3;
        smallestElementRepeatedExactlyKTimes(A, K);
  }
}
Smallest element with frequency K is: 2

सर्वात लहान घटक शोधण्यासाठी कॉम्प्लेक्सिटी विश्लेषण, नेमके के टाइम्स रिपीट केले

वेळ गुंतागुंत

आम्ही दोन आकाराचे लूप वापरत आहोत, दोन्ही आकार एन. म्हणून एकूण वेळ जटिलता आहे ओ (एन ^ 2).

जागेची जटिलता

आम्ही सतत जागा वापरत आहोत. तर अवकाश जटिलता आहे ओ (1).

दृष्टीकोन 2: हॅशिंग वापरुन

मुख्य कल्पना

आम्ही प्रत्येक घटकाची वारंवारता हॅश टेबलमध्ये ठेवू शकतो.

त्यानंतर, वारंवारतेसह सर्वात लहान घटक शोधण्यासाठी आम्ही हॅश टेबलमध्ये जाऊ शकतो.

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

  1. प्रत्येक घटक हॅश टेबलमध्ये असल्यास वारंवारता संचयित करा.
  2. असत्य सह व्हेरिएबल 'फ्लॅग' सुरू करा. आम्हाला फ्रिक्वेन्सी के सह काही घटक सापडले किंवा नसले तर ध्वजांकित करा.
  3. हॅश टेबलचे परीक्षण करा आणि वारंवारता के सह सर्वात लहान घटक शोधा.
  4. ध्वज सत्य असल्यास उत्तरे मुद्रित करा, अन्यथा मुद्रण करा की वारंवारता के बरोबर कोणतेही घटक नाहीत.

उदाहरणासह समजून घ्या

अ [] = {1, 2, 2, 5, 5, 2, 5}

के = 3

या अ‍ॅरेसाठी, हॅश टेबल असे दिसेल:

सर्वात लहान घटक अचूकपणे के टाइम्स पुनरावृत्ती

अंमलबजावणी

सी ++ प्रोग्राम

#include <bits/stdc++.h>
using namespace std;
void smallestElementRepeatedExactlyKTimes(vector<int> A, int K)
{
    int n = A.size();
    bool flag = false;
    int ans = 0;
    unordered_map<int, int> hash_table;
    for (int i = 0; i < n; i++)
    {
        hash_table[A[i]]++;
    }
    for (auto element : hash_table)
    {
        if (element.second == K)
        {
            if (flag == false)
            {
                flag = true;
                ans = element.first;
            }
            else
            {
                ans = min(ans, element.first);
            }
        }
    }
    if (flag == false)
    {
        cout << "There is no element with frequency K.";
    }
    else
    {
        cout << "Smallest element with frequency K is: " << ans;
    }
    return;
}
int main()
{
    vector<int> A = {1, 2, 2, 5, 5, 2, 5};
    int K = 3;
    smallestElementRepeatedExactlyKTimes(A, K);
    return 0;
}
Smallest element with frequency K is: 2

जावा कार्यक्रम

import java.util.*; 
public class Main
{
    static void smallestElementRepeatedExactlyKTimes(int A[],int K)
    {
        int n = A.length;
        boolean flag = false;
        int ans = 0;
        HashMap<Integer, Integer> hash_table = new HashMap<Integer, Integer>(); 
        for (int i = 0; i < n; i ++) 
        {
            if (hash_table.containsKey(A[i])) 
            {
                hash_table.put(A[i], hash_table.get(A[i]) + 1); 
            }
            else{
                hash_table.put(A[i], 1);
            }
        }
        for(Map.Entry element: hash_table.entrySet())
        {
            if(((int)element.getValue()==K))
            {
                if(flag==false)
                {
                    flag=true;
                    ans=((int)(element.getKey()));
                }
                else{
                    ans=Math.min(ans,((int)(element.getKey())));
                }
            }
        }
        if (flag == false)
        {
            System.out.print("There is no element with frequency K.");
        }
        else
        {
            System.out.print("Smallest element with frequency K is: "+ ans);
        }
        return;
    }
  public static void main(String[] args) {
    int A[] = {1, 2, 2, 5, 5, 2, 5};
        int K = 3;
        smallestElementRepeatedExactlyKTimes(A, K);
  }
}
Smallest element with frequency K is: 2

सर्वात लहान घटक शोधण्यासाठी कॉम्प्लेक्सिटी विश्लेषण, नेमके के टाइम्स रिपीट केले

वेळ गुंतागुंत

आम्ही केवळ एकदा अ‍ॅरेचा शोध घेत आहोत, म्हणून वेळ जटिलता आहे ओ (एन).

जागेची जटिलता

अ‍ॅरेमधील घटकांची वारंवारिता संग्रहित करण्यासाठी आम्ही हॅश टेबल ठेवत आहोत जेणेकरून स्पेसची जटिलता असेल ओ (एन).

संदर्भ