नक्कल समावेश गर्दछ


कठिनाई तह सजिलो
बारम्बार सोधिन्छ एडोब अमेजन एप्पल
एरे ह्याशिंग

हामीलाई दिइएको छ array र यसले नक्कल तत्त्वहरू समावेश गरेको हुन सक्छ वा हुन सक्दैन। त्यसैले हामीले जाँच गर्नु पर्छ कि यसमा नक्कल समावेश छ कि छैन।

उदाहरण

नक्कल समावेश गर्दछ

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

दृष्टिकोण

हामी विभिन्न तरीकाले एर्रे जाँच गर्न सक्छौं यसमा डुप्लिकेटहरू समावेश छन् कि छैनन् भनेर। सब भन्दा साधारण तरीका "ब्रुट फोर्स मेथड" हो। तर यो O (n) को एक समय जटिलता छ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

जटिलता विश्लेषण

समय जटिलता

O (n) जहाँ "n" एर्रेको आकार छ।

ठाउँ जटिलता

O (n) ह्यास तालिका द्वारा प्रयोग गरिएको खाली स्थानको रूपमा यसमा तत्वहरूको संख्या रेखीय छ।