Давхардсан агуулсан


Хэцүү байдлын түвшин Easy
Байнга асуудаг Adobe Амазоны Apple-ийн
Array Хаширч байна

Бидэнд массив мөн давхардсан элемент агуулсан байж магадгүй юм. Тиймээс давхардсан эсэхийг шалгах хэрэгтэй.

жишээ нь

Давхардсан агуулсан

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

арга барил

Бид массивыг давхардсан эсвэл агуулаагүй эсэхийг хэд хэдэн аргаар шалгаж болно. Хамгийн түгээмэл арга бол "Brute Force method" юм. Гэхдээ энэ нь O (n.) -Ийн цаг хугацааны нарийн төвөгтэй байдаг2) бөгөөд зөвхөн эрдэм шинжилгээний зорилгоор ашиглах боломжтой. Гэхдээ бид асуудлаа цаг хугацааны хувьд бага төвөгтэй байдлаар шийдвэрлэх өөр арга бол "Hash set method" эсвэл "Hash table method" энэ арга нь "Brute Force арга" -аас хамаагүй илүү үр дүнтэй юм. Hash Set арга нь O (n) -ийн цаг хугацааны нарийн төвөгтэй байдлыг шаарддаг.

Хэш тохируулах арга

Энэ арга нь бусдаас илүү энгийн бөгөөд үр дүнтэй байдаг. Энэ багц нь давхардсан агуулаагүй гэдгийг бид мэдэх хэрэгтэй. Хэрэв бид давхардсан утгыг нэмэхийг оролдвол алдаа гарах болно гэсэн үг юм. Хэрэв бид энэ аргыг хэрэглэвэл массивын элементүүдийг тойрон хүрээлэхэд л хангалттай. Хэш багцад оруулна уу. Дараа нь багцын хэмжээг массивтай харьцуулна уу. Хэрэв энэ нь тохируулсантай тэнцүү биш бол массив нь өөр биш давхардсан тоог агуулна.

Алгоритм

  1. Нэгдүгээрт, бид массивыг аргумент болгон авах функцийг бий болгодог.
  2. Үүний дараа бидний функцэд бид массивын бүх утгыг агуулсан багц үүсгэдэг.
  3. Set нь хуулбарыг зөвшөөрдөггүй, хэрэв массив нь давхардсан байвал түүний хэмжээ нь олонлогийн хэмжээнээс өөр байх болно гэсэн үг юм.
  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

Массив давхардсан эсэхийг шалгах Java код

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).