Рубрики

Найти первый повторяющийся символ в строке

Строки, Хеш

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

Примеры:

Input: ch = “geeksforgeeks”
Output: e
e is the first element that repeats

Input: str = “hello geeks”
Output: l
l is the first element that repeats

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

Сложность времени этого решения O (n 2 )

Мы можем использовать сортировку, чтобы решить проблему за O (n Log n) времени. Ниже приведены подробные шаги.

  • Скопируйте данный массив во вспомогательный массив temp [].
  • Сортируйте временный массив, используя алгоритм временной сортировки O (N log N).
  • Сканирование входного массива слева направо. Для каждого элемента подсчитайте его вхождения в temp [], используя бинарный поиск. Как только мы находим символ, встречающийся более одного раза, мы возвращаем его.

Этот шаг можно выполнить за O (N Log N).

Эффективным решением является использование хеширования для решения этого в среднем за O (N) времени.

  • Создайте пустой хеш.
  • Просканируйте каждый символ входной строки и вставьте значения в каждую из клавиш в хэше.
  • Когда какой-либо символ появляется более одного раза, значение хэш-ключа увеличивается на 1 и возвращает символ.

Ниже приведен пробный запуск вышеуказанного подхода:

Ниже приведена реализация вышеуказанного подхода:

C / C ++

// CPP программа для поиска первой
// повторяющийся символ в строке
#include <bits/stdc++.h>

using namespace std;

  
// Возвращает первый повторяющийся символ в str.

char firstRepeating(string &str)

{

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

    unordered_set<char> h;

  

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

    for (int i=0; i<str.length(); i++)

    {

        char c = str[i];

  

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

        // а затем сломать

        if (h.find(c) != h.end())

            return c;

  

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

            h.insert(c);

    }

  

    // Если не было повторяющегося символа

    return '\0';

}

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

int main ()

{

    string str = "geeksforgeeks";

    cout << firstRepeating(str);

    return 0;

}

Джава

// Java программа для поиска первой
// повторяющийся символ в строке

import java.util.*;

  

class Main

{

    // Эта функция печатает первый повтор

    // символ в строке []

    static char firstRepeating(char str[])

    {

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

        HashSet<Character> h = new HashSet<>();

  

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

        for (int i=0; i<=str.length-1; i++)

        {

            char c = str[i];

  

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

            // а затем сломать

            if (h.contains(c))

                return c;

  

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

                h.add(c);

        }

  

        return '\0';

    }

  

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

    public static void main (String[] args)

    {

        String str = "geeksforgeeks";

        char[] arr = str.toCharArray();

        System.out.println(firstRepeating(arr));

    }

}

питон

# Программа Python для поиска первой
# повторяющийся символ в строке

def firstRepeatedChar(str):

  

    h = {}  # Создать пустой хеш

  

    # Обход каждого символа в строке

    # в нижнем регистре

    for ch in str:

  

        # Если персонаж уже присутствует

        # в хеше, вернуть символ

        if ch in h:

            return ch;

  

        # Добавить ch в хеш

        else:

            h[ch] = 0

  

    return '\0'

  

  
# Код драйвера

print(firstRepeatedChar("geeksforgeeks"))

C #

// C # программа для поиска первой
// повторяющийся символ в строке

using System;

using System.Collections.Generic;

  

class GFG

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

public static char firstRepeating(char[] str)

{

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

    HashSet<char> h = new HashSet<char>();

  

    // Обход входного массива

    // слева направо

    for (int i = 0; i <= str.Length - 1; i++)

    {

        char c = str[i];

  

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

        // обновляем х и затем ломаем

        if (h.Contains(c))

        {

            return c;

        }

  

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

        {

            h.Add(c);

        }

    }

  

    return '\0';

}

  
// Код драйвера

public static void Main(string[] args)

{

    string str = "geeksforgeeks";

    char[] arr = str.ToCharArray();

    Console.WriteLine(firstRepeating(arr));

}
}

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

PHP

<?php 
// PHP программа для поиска первой повторной
// символ в строке

  
// Возвращает первый повторяющийся символ в str.

function firstRepeating($str)

{

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

    $h = array();

  

    // Обход входного массива

    // слева направо

    for ($i = 0; $i < strlen($str); $i++)

    {

        $c = $str[$i];

  

        // Если элемент уже в хэше

        // установить, обновить x и затем прервать

        if (array_search($c, $h))

            return $c;

  

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

            array_push($h, $c);

    }

  

    // Если не было повторяющегося символа

    return '\0';

}

  
// Код драйвера

$str = "geeksforgeeks";

echo firstRepeating($str);

  
// Этот код предоставлен ita_c
?>


Выход:

e

Аналогичная проблема: поиск первого неповторяющегося символа в строке .

Эта статья предоставлена Афзалом Ансари . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

Найти первый повторяющийся символ в строке

0.00 (0%) 0 votes