Рубрики

Найти первый повторяющийся элемент в массиве целых чисел

Учитывая массив целых чисел, найдите первый повторяющийся элемент в нем. Нам нужно найти элемент, который встречается более одного раза и чей индекс первого появления наименьший.

Примеры:

Input:  arr[] = {10, 5, 3, 4, 3, 5, 6}
Output: 5 [5 is the first element that repeats]

Input:  arr[] = {6, 10, 5, 4, 9, 120, 4, 6, 10}
Output: 6 [6 is the first element that repeats]

Простое решение заключается в использовании двух вложенных циклов. Внешний цикл выбирает элемент один за другим, внутренний цикл проверяет, повторяется ли элемент или нет. Как только мы находим элемент, который повторяется, мы разбиваем циклы и печатаем элемент. Сложность времени этого решения O (n 2 )

Мы можем использовать сортировку, чтобы решить проблему за O (nLogn) время. Ниже приведены подробные шаги.
1) Скопировать данный массив во вспомогательный массив temp [].
2) Сортировка временного массива с использованием алгоритма временной сортировки O (nLogn).
3) Сканирование входного массива слева направо. Для каждого элемента подсчитайте его вхождения в temp [], используя бинарный поиск . Как только мы находим элемент, который встречается более одного раза, мы возвращаем элемент. Этот шаг может быть выполнен за O (nLogn) время.

Мы можем использовать хеширование, чтобы решить это в среднем за O (n) раз. Идея состоит в том, чтобы обойти заданный массив справа налево и обновить минимальный индекс всякий раз, когда мы находим элемент, который был посещен справа. Спасибо Мохаммаду Шахиду за предложенное решение.

Ниже приводится реализация этой идеи.

C ++

/ * C ++ программа для поиска первого повторяющегося элемента в arr [] * /
#include<bits/stdc++.h>

using namespace std;

  
// Эта функция печатает первый повторяющийся элемент в arr []

void printFirstRepeating(int arr[], int n)

{

    // Инициализируем индекс первого повторяющегося элемента

    int min = -1;

  

    // Создает пустой хэшсет

    set<int> myset;

  

    // Обходим входной массив справа налево

    for (int i = n - 1; i >= 0; i--)

    {

        // Если элемент уже находится в хэш-наборе, обновить мин

        if (myset.find(arr[i]) != myset.end())

            min = i;

  

        else   // Остальное добавить элемент в хэш

            myset.insert(arr[i]);

    }

  

    // Распечатать результат

    if (min != -1)

        cout << "The first repeating element is " << arr[min];

    else

        cout << "There are no repeating elements";

}

  
// Метод драйвера для проверки вышеуказанного метода

int main()

{

    int arr[] = {10, 5, 3, 4, 3, 5, 6};

  

    int n = sizeof(arr) / sizeof(arr[0]);

    printFirstRepeating(arr, n);

}
// Эта статья предоставлена Чхави

Джава

/ * Java-программа для поиска первого повторяющегося элемента в arr [] * /

import java.util.*;

  

class Main

{

    // Эта функция печатает первый повторяющийся элемент в arr []

    static void printFirstRepeating(int arr[])

    {

        // Инициализируем индекс первого повторяющегося элемента

        int min = -1;

  

        // Создает пустой хэшсет

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

  

        // Обходим входной массив справа налево

        for (int i=arr.length-1; i>=0; i--)

        {

            // Если элемент уже находится в хэш-наборе, обновить мин

            if (set.contains(arr[i]))

                min = i;

  

            else   // Остальное добавить элемент в хэш

                set.add(arr[i]);

        }

  

        // Распечатать результат

        if (min != -1)

          System.out.println("The first repeating element is " + arr[min]);

        else

          System.out.println("There are no repeating elements");

    }

  

    // Метод драйвера для проверки вышеуказанного метода

    public static void main (String[] args) throws java.lang.Exception

    {

        int arr[] = {10, 5, 3, 4, 3, 5, 6};

        printFirstRepeating(arr);

    }

}

python3

# Python3 программа для поиска первого повторения
# элемент в arr []

  
# Эта функция печатает первый повторяющийся
# элемент в arr []

def printFirstRepeating(arr, n):

  

    # Инициализировать индекс первого повторяющегося элемента

    Min = -1

  

    # Создает пустой хэшсет

    myset = dict()

  

    # Обход входного массива справа налево

    for i in range(n - 1, -1, -1):

      

        # Если элемент уже находится в хэш-наборе,

        # обновление Мин

        if arr[i] in myset.keys():

            Min = i

  

        else: # Еще добавить элемент в хэш-набор

            myset[arr[i]] = 1

      

    # Распечатать результат

    if (Min != -1):

        print("The first repeating element is"

                                      arr[Min])

    else:

        print("There are no repeating elements")

  
Код водителя

arr = [10, 5, 3, 4, 3, 5, 6]

  

n = len(arr)

printFirstRepeating(arr, n)

  
# Этот код предоставлен Мохитом Кумаром 29

C #

using System;

using System.Collections.Generic;

  
/ * C # программа для поиска первого повторяющегося элемента в arr [] * /

  

public class GFG

{

    // Эта функция печатает первый повторяющийся элемент в arr []

    public static void printFirstRepeating(int[] arr)

    {

        // Инициализируем индекс первого повторяющегося элемента

        int min = -1;

  

        // Создает пустой хэшсет

        HashSet<int> set = new HashSet<int>();

  

        // Обходим входной массив справа налево

        for (int i = arr.Length - 1; i >= 0; i--)

        {

            // Если элемент уже находится в хэш-наборе, обновить мин

            if (set.Contains(arr[i]))

            {

                min = i;

            }

  

            else // Остальное добавить элемент в хэш

            {

                set.Add(arr[i]);

            }

        }

  

        // Распечатать результат

        if (min != -1)

        {

          Console.WriteLine("The first repeating element is " + arr[min]);

        }

        else

        {

          Console.WriteLine("There are no repeating elements");

        }

    }

  

    // Метод драйвера для проверки вышеуказанного метода

  

    public static void Main(string[] args)

    {

        int[] arr = new int[] {10, 5, 3, 4, 3, 5, 6};

        printFirstRepeating(arr);

    }

}

  
// Этот код предоставлен Shrikant13

Выход:

The first repeating element is 5

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Найти первый повторяющийся элемент в массиве целых чисел

0.00 (0%) 0 votes