തനിപ്പകർപ്പ് അടങ്ങിയിരിക്കുന്നു


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു അഡോബി ആമസോൺ ആപ്പിൾ
അറേ ഹാഷിംഗ്

ഞങ്ങൾക്ക് ഒരു നൽകിയിട്ടുണ്ട് ശ്രേണി അതിൽ തനിപ്പകർപ്പ് ഘടകങ്ങൾ അടങ്ങിയിരിക്കാം അല്ലെങ്കിൽ ഉണ്ടാകില്ല. അതിനാൽ അതിൽ തനിപ്പകർപ്പ് ഉണ്ടോ എന്ന് പരിശോധിക്കേണ്ടതുണ്ട്.

ഉദാഹരണങ്ങൾ

തനിപ്പകർപ്പ് അടങ്ങിയിരിക്കുന്നു

[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. അവസാനമായി, അറേയുടെയും സെറ്റിന്റെയും വലുപ്പം ഞങ്ങൾ താരതമ്യം ചെയ്യുന്നു. അവയുടെ വലുപ്പത്തിൽ വ്യത്യാസമുണ്ടെങ്കിൽ‌, അറേയിൽ‌ തനിപ്പകർ‌പ്പുകൾ‌ അടങ്ങിയിരിക്കുന്നു, അല്ലെങ്കിൽ‌ എല്ലാ ഘടകങ്ങളും വ്യത്യസ്‌തമാണ്.

വിശദീകരണം

ഞങ്ങളുടെ പ്രോഗ്രാമിൽ തനിപ്പകർപ്പുകൾ പരിശോധിക്കാൻ ഞങ്ങൾ ഹാഷ് സെറ്റ് ഉപയോഗിക്കുന്നു ആദ്യം, പരിശോധിക്കുന്നതിന് ഞങ്ങൾ ഒരു ഫംഗ്ഷൻ നടത്തും. അതിൽ ഞങ്ങൾ ഒരു ഹാഷ് സെറ്റ് നിർമ്മിക്കുകയും അറേയുടെ എല്ലാ മൂല്യങ്ങളും നൽകുകയും ചെയ്യും. ആ സെറ്റിന് ശേഷം തനിപ്പകർ‌പ്പുകൾ‌ അടങ്ങിയിട്ടുണ്ടെങ്കിൽ‌ അത് നീക്കംചെയ്യുന്നു, കൂടാതെ അറേയുമായി താരതമ്യപ്പെടുത്തുമ്പോൾ‌ അതിന്റെ വലുപ്പം വ്യത്യസ്തമായിരിക്കും, അത് സെറ്റിന്റെ വലുപ്പത്തെ ബാധിക്കുകയില്ല.

അറേയിൽ തനിപ്പകർപ്പുകൾ ഉണ്ടോയെന്ന് പരിശോധിക്കാൻ സി ++ കോഡ്

#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) ഒരു ഹാഷ് പട്ടിക ഉപയോഗിക്കുന്ന ഇടം അതിലെ ഘടകങ്ങളുടെ എണ്ണവുമായി രേഖീയമാണ്.