మూలకాలు పరిధికి పరిమితం కానప్పుడు ఇచ్చిన శ్రేణిలో నకిలీలను కనుగొనండి


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది Adobe అమెజాన్ ఫాక్ట్‌సెట్ మాక్య్ UHG ఆప్టం
అర్రే హ్యాషింగ్

“మూలకాలు పరిధికి పరిమితం కానప్పుడు ఇచ్చిన శ్రేణిలో నకిలీలను కనుగొనండి” అనే సమస్య మీకు ఉందని పేర్కొంది అమరిక n కలిగి పూర్ణాంకాల. శ్రేణిలో ఉంటే నకిలీ మూలకాలను తెలుసుకోవడానికి సమస్య స్టేట్‌మెంట్. అటువంటి మూలకం లేకపోతే తిరిగి -1.

ఉదాహరణ

మూలకాలు పరిధికి పరిమితం కానప్పుడు ఇచ్చిన శ్రేణిలో నకిలీలను కనుగొనండి

[ 2, 4, 6, 2, 7, 8, 9, 7]
2, 7

వివరణ

ఈ శ్రేణిలో 2 మరియు 7 మాత్రమే నకిలీ అంశాలు.

[134, 567, 134, 456, 1000, 567, 7]
134, 567

వివరణ

ఈ శ్రేణిలో 134 మరియు 567 మాత్రమే నకిలీ అంశాలు.

శ్రేణిలో నకిలీ అంశాలను కనుగొనడానికి అల్గోరిథం

  1. డిక్లేర్ చిహ్నం.
  2. శ్రేణి యొక్క మూలకం మరియు దాని పౌన frequency పున్యాన్ని మ్యాప్‌లో నిల్వ చేయండి.
  3. ప్రకటించండి బూలియన్ వేరియబుల్ నకిలీ నకిలీ మూలకం ఉందో లేదో తనిఖీ చేయడానికి.
  4. మ్యాప్ మీద మళ్ళించండి మరియు 1 కంటే ఎక్కువ ఫ్రీక్వెన్సీ ఉన్న మూలకం కోసం తనిఖీ చేయండి.
  5. ఫ్రీక్వెన్సీ 1 కన్నా ఎక్కువ ఉంటే, మూలకాన్ని ప్రింట్ చేసి, నకిలీని ఒప్పుకు ప్రారంభించండి.
  6. పరిస్థితి సంతృప్తికరంగా ఉంటే నకిలీ తప్పు కాదా అని తనిఖీ చేసి -1 ముద్రించండి.

వివరణ

మేము ఒక శ్రేణిలోని నకిలీ మూలకాలను నిర్ణయించి, ఆ మూలకాలను ముద్రించాల్సిన సమస్యను ఇచ్చాము. దీని కోసం, మేము a ను ఉపయోగించబోతున్నాము హాష్ మ్యాప్ ప్రతి శ్రేణి మూలకం యొక్క పౌన encies పున్యాలను నిల్వ చేయడానికి. 1 కంటే ఎక్కువ ఉండే ఫ్రీక్వెన్సీలు అంటే, శ్రేణిలో సంఖ్య పునరావృతమవుతుంది. అంటే ఆ సంఖ్య యొక్క నకిలీ.

మేము రెండు వాదనలను శ్రేణి మరియు దాని పొడవుగా ఆమోదించాము. ఇప్పుడు బూలియన్ వేరియబుల్ తప్పుడు అని ప్రారంభించిన మరో వేరియబుల్ ప్రకటించండి. తరువాత దాన్ని తనిఖీ చేయండి, అప్పుడు మనకు ఏ నకిలీ మూలకం కనిపించకపోతే నకిలీ అది నిజం అవుతుంది. ఈ మ్యాప్‌ను ఉపయోగించి, 1 కంటే ఎక్కువ ఫ్రీక్వెన్సీ ఉన్న మూలకాన్ని కనుగొనండి, మేము ఆ మూలకాలను ప్రింట్ చేస్తాము. మరియు మేము శ్రేణిలో నకిలీ అంశాలను ఎలా కనుగొంటాము.

ఒక ఉదాహరణను పరిశీలిద్దాం:

arr [] = {2,4,6,3,1,2,4,7};

i = 0, arr [i] = 2; ఫ్రీక్ = {2: 1}

i=1, arr[i]=4; freq={2:1,4:1}

i=2, arr[i]=6; freq={2:1,4:1,6:1}

i=3, arr[i]=3; freq={2:1,4:1,6:1,3:1}

i=4, arr[i]=1; freq={2:1,4:1,6:1,3:1,1:1}

i = 5, arr [i] = 2; freq = {2: 2,4: 1,6: 1,3: 1,1: 1} // '2' యొక్క ఫ్రీక్వెన్సీని 1 నుండి 2 కి పెంచుతుంది,

i = 6, arr [i] = 4; freq = {2: 2,4: 2,6: 1,3: 1,1: 1} // '4' యొక్క ఫ్రీక్వెన్సీని 1 నుండి 2 కి పెంచుతుంది,

i=7, arr[i]=7; freq={2:2,4:2,6:1,3:1,1:1,7:1}

మాప్‌లో ఫ్రీక్ ఉంది: {2: 2,4: 2,6: 1,3: 1,1: 1,7: 1}

ఇప్పుడు మ్యాప్‌లో మళ్ళించండి మరియు ఏ విలువ 1 కంటే ఎక్కువగా ఉందో తెలుసుకోండి. మేము ఇప్పటికే ఇక్కడ బూలియన్ వేరియబుల్ డూప్లికేట్‌ను తప్పుడు అని ప్రారంభించాము, కాబట్టి 1 కంటే ఎక్కువ ఫ్రీక్వెన్సీ ఉందని తనిఖీ చేసినప్పుడు మేము నకిలీని ట్రూగా అప్‌డేట్ చేయబోతున్నాం. మరియు మేము తప్పుడు నకిలీ కలిగి ఉన్న లూప్ నుండి బయటకు వస్తే, దాని అర్ధం నకిలీ మూలకం శ్రేణిలో లేదు.

స్పష్టంగా, 2 మరియు 4 అవి నకిలీ మూలకాలు అని అర్ధం కంటే ఎక్కువ పౌన frequency పున్యాన్ని కలిగి ఉంటాయి.

మరియు మా అవుట్పుట్ [2 4] అవుతుంది. కాబట్టి శ్రేణిలో నకిలీ మూలకాలను మేము ఎలా కనుగొంటాము అనేదానికి ఇది ఒక ఉదాహరణ.

కోడ్

శ్రేణిలో నకిలీ అంశాలను కనుగొనడానికి C ++ కోడ్

#include <iostream>
#include <unordered_map>

using namespace std;

void getDuplicate(int arr[], int n)
{
    unordered_map<int,int> freq;

    for(int index=0;index<n;index++)
        freq[arr[index]]++;

    bool duplicate=false;
    unordered_map<int,int> :: iterator itr;
    for(itr=freq.begin();itr!=freq.end();itr++)
    {
        if(itr->second > 1)
        {
            cout<<itr->first<<" ";
            duplicate=true;
        }
    }
    if(!duplicate)
        cout<<"-1"<<endl;
}
int main()
{
    int arr[]={2,4,6,3,1,2,4,7};
    int n=sizeof(arr)/sizeof(arr[0]);
    getDuplicate(arr,n);
    return 0;
}
4 2

శ్రేణిలో నకిలీ అంశాలను కనుగొనడానికి జావా కోడ్

import java.util.HashMap;
class findDuplicateNumber
{
    public static void getDuplicate(int arr[], int n)
    {
        HashMap<Integer, Integer> freq=new HashMap<Integer, Integer>();
        for(int i=0; i<n; i++)
        {
            if(freq.containsKey(arr[i]))
            {
                freq.put(arr[i],freq.get(arr[i])+1);
            }
            else
            {
                freq.put(arr[i],1);
            }
        }
        boolean duplicate=false;
        for(int i:freq.keySet())
        {
            if(freq.get(i)> 1)
            {
                System.out.print(i+" ");
                duplicate=true;
            }
        }
        if(!duplicate)
            System.out.println("-1");
    }
    public static void main(String [] args)
    {
        int arr[]= {2,4,6,3,1,2,4,7};
        int len=arr.length;
        getDuplicate(arr,len);
    }
}
2 4

సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

పై)  (ఇక్కడ “N” శ్రేణిలోని మూలకాల సంఖ్య. అందువల్ల “మూలకాలు పరిధికి పరిమితం కానప్పుడు ఇచ్చిన శ్రేణిలో నకిలీలను కనుగొనండి” సమస్య సరళ సమయ సంక్లిష్టతను కలిగి ఉంటుంది.

అంతరిక్ష సంక్లిష్టత

పై)  (ఇక్కడ “N” శ్రేణిలోని మూలకాల సంఖ్య. స్థల సంక్లిష్టత కూడా సరళంగా ఉంటుంది, ఎందుకంటే చెత్త సందర్భంలో మనకు అన్ని విభిన్న అంశాలు ఉండవచ్చు.