ડુપ્લિકેટ સમાવે છે


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એડોબ એમેઝોન સફરજન
અરે હેશિંગ

અમને આપવામાં આવે છે એક એરે અને તેમાં ડુપ્લિકેટ્સ તત્વો હોઈ શકે છે અથવા કદાચ નહીં. તેથી આપણે તપાસવાની જરૂર છે કે તેમાં ડુપ્લિકેટ છે કે કેમ.

ઉદાહરણો

ડુપ્લિકેટ સમાવે છે

[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

જટિલતા વિશ્લેષણ

સમય જટિલતા

O (n) જ્યાં "n" એરેનું કદ છે.

અવકાશ જટિલતા

ઓ (એન) હેશ ટેબલ દ્વારા ઉપયોગમાં લેવાતી જગ્યા તેમાં તત્વોની સંખ્યા સાથે રેખીય છે.