నకిలీ కలిగి ఉంటుంది


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

మాకు ఒక ఇవ్వబడింది అమరిక మరియు అది నకిలీ మూలకాలను కలిగి ఉండవచ్చు లేదా కాకపోవచ్చు. కనుక ఇది నకిలీ కలిగి ఉందో లేదో తనిఖీ చేయాలి.

ఉదాహరణలు

నకిలీ కలిగి ఉంటుంది

[1, 3, 5, 1]
true
[“apple”, “mango”, “orange”, “mango”]
true
[22.0, 4.5, 3.98, 45.6, 13.54]
false

అప్రోచ్

శ్రేణిలో నకిలీలు ఉన్నాయా లేదా అని తనిఖీ చేయడానికి మేము అనేక విధాలుగా తనిఖీ చేయవచ్చు. అత్యంత సాధారణ పద్ధతి “బ్రూట్ ఫోర్స్ పద్ధతి”. కానీ దీనికి O (n) యొక్క సమయ సంక్లిష్టత ఉంది2) మరియు ఇది విద్యా ప్రయోజనాల కోసం మాత్రమే మంచిది. కానీ మన సమస్యను తక్కువ సమయ సంక్లిష్టత “హాష్ సెట్ పద్ధతి” లేదా “హాష్ టేబుల్ పద్ధతి” లో పరిష్కరించడానికి మరొకరు ఈ పద్ధతి “బ్రూట్ ఫోర్స్ పద్ధతి” కంటే చాలా సమర్థవంతంగా పనిచేస్తుంది. హాష్ సెట్ పద్ధతి O (n) యొక్క సమయ సంక్లిష్టతను తీసుకుంటుంది.

హాష్ సెట్ పద్ధతి

ఈ పద్ధతి ఇతరులకన్నా సరళమైనది మరియు సమర్థవంతమైనది. ఆ సెట్‌లో నకిలీలు ఉండవని మనం తెలుసుకోవాలి. అంటే మనం నకిలీ విలువను సెట్ చేయడానికి ప్రయత్నిస్తే అది లోపం ఇస్తుంది. మేము ఈ పద్ధతిని ఉపయోగిస్తే, మనం చేయాల్సిందల్లా శ్రేణి మూలకాలపై లూప్ చేసి, వాటిని హాష్ సెట్‌లోకి చొప్పించండి. అప్పుడు సెట్ యొక్క పరిమాణాన్ని శ్రేణికి సరిపోల్చండి. ఇది సెట్ చేయడానికి సమానం కాకపోతే, అర్రే నకిలీలను కలిగి ఉంటుంది.

అల్గారిథం

  1. మొదట, మేము శ్రేణిని వాదనగా తీసుకునే ఫంక్షన్‌ను సృష్టిస్తాము.
  2. ఆ తరువాత, మా ఫంక్షన్‌లో, మేము శ్రేణి యొక్క అన్ని విలువలను కలిగి ఉన్న సమితిని సృష్టిస్తాము.
  3. సెట్ నకిలీలను అనుమతించదు, అంటే శ్రేణి నకిలీలను కలిగి ఉంటే దాని పరిమాణం సెట్ పరిమాణం కంటే భిన్నంగా ఉంటుంది.
  4. చివరగా, మేము శ్రేణి మరియు సెట్ రెండింటి పరిమాణాన్ని పోల్చాము. వాటి పరిమాణంలో వ్యత్యాసం ఉంటే, శ్రేణిలో నకిలీలు ఉంటాయి, లేకపోతే అన్ని అంశాలు విభిన్నంగా ఉంటాయి.

వివరణ

మా ప్రోగ్రామ్‌లో మేము నకిలీలను తనిఖీ చేయడానికి హాష్ సెట్‌ను ఉపయోగిస్తాము మొదట, మేము తనిఖీ చేయడానికి ఒక ఫంక్షన్ చేస్తాము. దీనిలో మేము హాష్ సెట్ చేసి, శ్రేణి యొక్క అన్ని విలువలను ఇస్తాము. ఆ సెట్ తరువాత నకిలీలను కలిగి ఉంటే దాన్ని తీసివేస్తుంది మరియు శ్రేణితో పోల్చితే దాని పరిమాణం భిన్నంగా ఉంటుంది, అది సెట్ యొక్క పరిమాణాన్ని ప్రభావితం చేయదు.

శ్రేణిలో నకిలీలు ఉన్నాయో లేదో తనిఖీ చేయడానికి C ++ కోడ్

#include <iostream>
#include <unordered_set>
using namespace std;

bool contain_duplicate(int arr[], int n)
{
    unordered_set<int> myset;
    bool flag = 0;

    for (int i = 0; i < n; i++)
    {
        if (myset.find(arr[i]) == myset.end())
            myset.insert(arr[i]);

        else
        {
            flag = 1;
            break;
        }

    }
    return flag;
}
int main()
{
    int arr[] = {1, 5, 2, 4, 3, 7, 8, 9, 1};
    int n = sizeof(arr) / sizeof(int);

    cout<< boolalpha <<contain_duplicate(arr, n);
    return 0;
}
true

శ్రేణిలో నకిలీలు ఉన్నాయో లేదో తనిఖీ చేయడానికి జావా కోడ్

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

class contain_duplicate
{

    public static boolean solution(Integer [] array)
    {

        Set<Integer> myset = new HashSet<> (Arrays.asList(array));

        if(array.length!=myset.size())
        {
            return true;
        }
        else
        {
            return false;
        }
    }

    public static void main(String[] args)
    {
        Integer [] array = { 1, 2, 3, 6, 4, 9, 8, 1};
        System.out.println(solution(array));

    }
}
true

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

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

O (n) ఇక్కడ “n” అనేది శ్రేణి యొక్క పరిమాణం.

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

O (n) హాష్ పట్టిక ఉపయోగించే స్థలం దానిలోని మూలకాల సంఖ్యతో సరళంగా ఉంటుంది.