Аввалин элементи такрори массиви бутунро ёбед


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Amazon Фараж MAQ Microsoft Oracle
тартиботи ҳарбӣ Хашм

Изҳороти мушкилот

Аввалин унсури такроршавандаро дар an ёбед асал проблемаи бутунҳо мегӯяд, ки ба шумо массиви бутун дода мешавад. Он дархост мекунад, ки аввалин элементи такроршавандаро аз массив ёфта, ин рақамро чоп кунед.

мисол

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 бошад, ин маънои онро дорад, ки мо ягон унсури такроршавандаро наёфтем, агар он навсозӣ шуда бошад, пас мо арзиши индекси парчами массивро чоп мекунем.

рамз

Коди 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 барои пайдо кардани як аломати такрори аввал

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) дохил ва ҷустуҷӯ кунем.

Мураккабии фазо

Эй (н) ки дар "Н" шумораи унсурҳои массив аст.