Съдържа дубликат


Ниво на трудност Лесно
Често задавани в Кирпич Амазонка ябълка
Array хеширане

Дадено ни е масив и може да съдържа дублиращи се елементи или може би не. Затова трябва да проверим дали съдържа дубликат.

Примери

Съдържа дубликат

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

Подход

Можем да проверим масив по няколко начина, за да проверим дали съдържа дубликати или не. Най-често срещаният метод е „методът на груба сила“. Но има времева сложност на O (n2) и е добър само за академични цели. Но ние трябва да решим проблема си с по-малка сложност “Метод на хеш набор” или “Метод на хеш таблица”, този метод е много по-ефективен от “метода на грубата сила”. Методът Hash Set отнема времевата сложност на O (n).

Метод за задаване на хеш

Този метод е дори по-опростен и ефективен от други. Всичко, което трябва да знаем, че наборът не съдържа дубликати. Това означава, че ако се опитаме да добавим дублирана стойност, е зададена грешка. Ако използваме този метод, всичко, което трябва да направим, е просто да прекачим елементите на масива, да ги вмъкнем в хеш набора. След това сравнете размера на набора с масива. Ако не е равно на set, масивът съдържа дубликати, но не.

алгоритъм

  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), тъй като пространството, използвано от хеш таблица, е линейно с броя на елементите в нея.