Знайдіть перший повторюваний елемент у масиві цілих чисел


Рівень складності Легко
Часто запитують у Амазонка Фанатики MAQ Microsoft оракул
масив Хешування

Постановка проблеми

Знайдіть перший повторюваний елемент у масив цілих чисел проблема стверджує, що вам дано масив цілих чисел. Він просить виявити перший повторюваний елемент із масиву та надрукувати це число.

Приклад

arr[] = {2,6,9,3,1,9,1}
9

Пояснення: У даному масиві є два числа, які повторюються, але першим повторенням є 9.

arr[] = {1,4,7,0,2,5}
No repeating number.

Пояснення: У даному масиві немає повторюваного числа.

Алгоритм пошуку першого повторюваного персонажа

1. Set flag to -1.
2. Declare a Set.
3. Start traversing the array from the right to left.
    1. If the number is repeating then update the value of flag to the index of the current array element.
    2. Else, insert the each array’s element into the declared set.
4. Check if flag value is still -1, then we have found no repeating element.
5. Else print flag index position of array.

Пояснення

Знайдіть перший повторюваний елемент у масиві цілих чисел

 

Ми дали масив цілих чисел, ми попросили з’ясувати, чи є повторюваний елемент після друку, але умовою є те, що число в масиві має бути першим повторюваним елементом. Число, яке повторюється першим у масиві, буде необхідною відповіддю, тобто чому ми обходимо його справа наліво. Ми будемо використовувати набір. Set має функцію не зберігати загальні елементи в Set. Отже, коли ми знайшли одне, що повторюється в масиві, ми просто отримуємо його індекс, а потім друкуємо елемент цього індексу.

Ми оголосимо набір, почнемо обхід праворуч від масиву, ми перевіримо, чи набір вже містить значення поточного елемента масиву, якщо він містить, тоді отримаємо його індекс і оновимо значення прапора до цього індексу, це значення прапора ми буде використовувати його як індекс, а пізніше ми будемо друкувати це значення.

До цього нам слід вставити всі значення масиву під час обходу, тому, коли ми отримаємо подібне значення, ми будемо зберігати індекс цього елемента. Хоча ми обходимо масив справа, якщо ми знайшли якийсь елемент праворуч, який повторюється ліворуч, це означає, що це перший повторюваний елемент. Ми оновлюємо значення прапора, оскільки пізніше ми перевіримо, чи все ще значення прапора дорівнює -1, чи воно оновлено. Якщо воно все ще -1, це означає, що ми не знайшли жодного повторюваного елемента, якщо його оновити, ми надрукуємо значення індексу прапора масиву.

код

Код С ++ для пошуку першого повторюваного символу

#include<bits/stdc++.h>

using namespace std;

void getFirstRepeatedElement(int arr[], int n)
{
    int Flag = -1;

    unordered_set<int> SET;

    for (int i = n - 1; i >= 0; i--)
    {
        if (SET.find(arr[i]) != SET.end())
            Flag = i;

        else
            SET.insert(arr[i]);
    }
    if (Flag!= -1)
        cout << "The first repeating element is " << arr[Flag];
    else
        cout << "There are no repeating elements";
}
int main()
{
    int arr[] = {2,6,9,3,1,9,1};

    int n = sizeof(arr) / sizeof(arr[0]);
    getFirstRepeatedElement (arr, n);
}
The first repeating element is 9

Java-код, щоб знайти перший повторюваний символ

import java.util.HashSet;

class FirstRepeatingElement
{
    public static void getFirstRepeatedElement (int arr[])
    {
        int Flag = -1;

        HashSet<Integer> SET = new HashSet<>();

        for (int i=arr.length-1; i>=0; i--)
        {
            if (SET.contains(arr[i]))
                Flag = i;

            else
                SET.add(arr[i]);
        }
        if (Flag!= -1)
            System.out.println("First repeating element is " + arr[Flag]);
        else
            System.out.println("No repeated element");
    }
    public static void main (String[] args)
    {
        int arr[] = {2,6,9,3,1,9,1};
        getFirstRepeatedElement(arr);
    }
}
First repeating element is 9

Аналіз складності

Складність часу

О (п) де "N" - кількість елементів у масиві. Оскільки ми використовуємо HashSet, ми можемо виконувати вставку та пошук в операціях O (1).

Складність простору

О (п) де "N" - кількість елементів у масиві.