අනුපිටපත් අඩංගු වේ


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ඇෙබෝ ඇමේසන් Apple ජංගම දුරකථන
අරා හැෂිං

අපට ලබා දී ඇත්තේ අ අරාව එය අනුපිටපත් මූලද්‍රව්‍ය අඩංගු විය හැකිය. එබැවින් එහි අනුපිටපත් තිබේදැයි පරීක්ෂා කර බැලිය යුතුය.

උදාහරණ

අනුපිටපත් අඩංගු වේ

[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) හැෂ් වගුවක් භාවිතා කරන අවකාශය එහි ඇති මූලද්‍රව්‍ය ගණන සමඟ රේඛීය වේ.