Пронађите први понављајући елемент у низу целих бројева


Ниво тешкоће Лако
Често питани у амазонка Фанатици МАК мицрософт пророчанство
Ред Хасхинг

Изјава о проблему

Пронађите први понављајући елемент у поредак целог броја проблем наводи да сте добили низ целих бројева. Тражи да се из низа открије први понављајући елемент и испише тај број.

Пример

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.

Објашњење

Пронађите први понављајући елемент у низу целих бројева

 

Дали смо низ целих бројева, тражили смо да пронађемо има ли понављајући елемент, а затим исписати, али услов је да број у низу буде први понављајући елемент. Број који се први понавља у низу биће тражени одговор, односно зашто га прелазимо здесна налево. Користићемо сет. Сет има функцију да не чува уобичајене елементе у Сету. Дакле, када смо пронашли једно понављање у низу, једноставно добијемо његов индекс и потом одштампамо елемент тог индекса.

Прогласићемо скуп, започети обилазак с десне стране низа, проверићемо да ли скуп већ садржи вредност тренутног елемента низа ако садржи, затим добити његов индекс и ажурирати вредност заставе на тај индекс, вредност ове заставице коју користимо користиће га као индекс, а касније ћемо исписати ту вредност.

Пре тога, требало би да уметнемо све вредности низа током обилажења, па ћемо, када добијемо сличну вредност, сачувати индекс тог елемента. Иако прелазимо низ с десне стране, ако смо пронашли било који елемент у десној страни који се понавља у левој, то значи да је то први понављајући елемент. Ажурирамо вредност заставице јер ћемо касније проверавати да ли је вредност заставе и даље -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

Јава код за проналажење првог понављајућег карактера

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

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

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

Он) где „Н“ је број елемената у низу. Будући да користимо ХасхСет, можемо да извршимо уметање и претрагу у операцијама О (1).

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

Он) где „Н“ је број елемената у низу.