डुप्लिकेट आहे


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

आम्हाला एक दिले जाते अॅरे आणि त्यात कदाचित डुप्लिकेट घटक असू शकतात किंवा नसू शकतात. तर त्यात डुप्लिकेट आहे की नाही हे तपासण्याची गरज आहे.

उदाहरणे

डुप्लिकेट आहे

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

दृष्टीकोन

त्यात डुप्लिकेट्स आहेत की नाही हे तपासण्यासाठी आम्ही अ‍ॅरे बर्‍याच मार्गांनी तपासू शकतो. सर्वात सामान्य पद्धत म्हणजे “ब्रूट फोर्स मेथड”. परंतु त्यास ओ (एन) ची एक वेळ जटिलता आहे2) आणि केवळ शैक्षणिक उद्देशाने ते चांगले आहे. परंतु आम्ही कमी वेळात आमच्या समस्येचे निराकरण करण्यासाठी “हॅश सेट मेथड” किंवा “हॅश टेबल मेथड” ही पद्धत “ब्रूट फोर्स मेथड” पेक्षा अधिक कार्यक्षम आहे. हॅश सेट पद्धत ओ (एन) ची जटिलता घेते.

हॅश सेट पद्धत

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

अल्गोरिदम

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

स्पष्टीकरण

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

अ‍ॅरेमध्ये डुप्लिकेट आहेत का ते तपासण्यासाठी सी ++ कोड

#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

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

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

ओ (एन) जेथे अ‍ॅरेचा आकार “एन” आहे.

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

ओ (एन) हॅश टेबलद्वारे वापरलेली जागा त्यातील घटकांच्या संख्येसह रेषात्मक आहे.