Намерете първия повтарящ се елемент в масив от цели числа


Ниво на трудност Лесно
Често задавани в Амазонка Фанатиците Maq Microsoft Оракул
Array хеширане

Декларация за проблема

Намерете първия повтарящ се елемент в масив на цели числа проблемът гласи, че ви е даден масив от цели числа. Той иска да открие първия повтарящ се елемент от масива и да отпечата това число.

Пример

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, това означава, че не сме намерили повтарящ се елемент, ако се актуализира, ще отпечатаме стойността на индекса на флага на масив.

код

C ++ код за намиране на първи повтарящ се символ

#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 Code за намиране на първи повтарящ се символ

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

Анализ на сложността

Сложност във времето

О (п) където "н" е броят на елементите в масива. Тъй като използваме HashSet, можем да извършваме вмъкване и търсене в операции O (1).

Сложност на пространството

О (п) където "н" е броят на елементите в масива.