Найти первый неповторенный символ в строке

Question

Какой самый быстрый способ найти первый символ, который появляется в строке только один раз?

Answer 1

Должно быть как минимум O (n), потому что вы не знаете, будет ли повторяться символ, пока не прочитаете все символы.

Таким образом, вы можете перебирать символы и добавлять каждый символв первый раз, когда вы видите его, и отдельно ведите подсчет того, сколько раз вы его видели (на самом деле значения имеют значение только «0», «1» или «более 1»).

Когда вы достигнете конца строки, вам просто нужно найти первый символ в списке, который имеет счетчик ровно один.

---

Пример кода на Python:

def first_non_repeated_character(s):
    counts = defaultdict(int)
    l = []
    for c in s:
        counts[c] += 1
        if counts[c] == 1:
            l.append(c)

    for c in l:
        if counts[c] == 1:
            return c

    return None

Это выполняется в O (n).

Answer 2

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

def first_non_repeated_character(string):
  chars = []
  repeated = []
  for character in string:
    if character in chars:
      chars.remove(character)
      repeated.append(character)
    else:
      if not character in repeated:
        chars.append(character)
  if len(chars):
    return chars[0]
  else:
    return False

Редактировать: изначально опубликованный код был неверным, но этот последний фрагмент сертифицирован для работы на компьютере Райана ™.

Answer 3

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

Answer 4

Вот еще один интересный способ сделать это. Для счетчика требуется Python2.7 или Python3.1

>>> from collections import Counter
>>> def first_non_repeated_character(s):
...     return min((k for k,v in Counter(s).items() if v<2), key=s.index)
...
>>> first_non_repeated_character("aaabbbcddd")
'c'
>>> first_non_repeated_character("aaaebbbcddd")
'e'

Answer 5

Многие ответы пытаются O (n), но забывают о фактических затратах на вставку и удаление из списков / ассоциативных массивов / наборов, которые они используют для отслеживания.

Если вы можете предположить, что символ представляет собой один байт, тогда вы используете простой массив, индексированный символом, и сохраняете в нем счет. Это действительно O (n), потому что доступ к массиву гарантирован O (1), и последний проход по массиву для поиска первого элемента с 1 - это постоянное время (потому что массив имеет небольшой фиксированный размер).

Если вы не можете предположить, что символ представляет собой один байт, я бы предложил отсортировать строку и затем выполнить один проход, проверяя смежные значения. Это будет O (n log n) для сортировки плюс O (n) для последнего прохода. Таким образом, это фактически O (n log n), что лучше, чем O (n ^ 2). Кроме того, он практически не имеет места, что является еще одной проблемой для многих ответов, которые пытаются O (n).

Answer 6

Для счетчика требуется Python2.7 или Python3.1

>>> from collections import Counter
>>> def first_non_repeated_character(s):
...     counts = Counter(s)
...     for c in s:
...         if counts[c]==1:
...             return c
...     return None
... 
>>> first_non_repeated_character("aaabbbcddd")
'c'
>>> first_non_repeated_character("aaaebbbcddd")
'e'

Answer 7

Рефакторинг решения, предложенного ранее (без необходимости использования дополнительного списка / памяти). Это проходит через строку дважды. Так что для O (n) это тоже самое, что и для исходного решения.

def first_non_repeated_character(s):
    counts = defaultdict(int)
    for c in s:
        counts[c] += 1
    for c in s:
        if counts[c] == 1:
            return c
    return None

Answer 8

Я думаю, что это должно быть сделано в C. Это работает за O (n) время, без двусмысленности относительно порядка вставки и удаления операторов.Это сортировочная сортировка (простейшая форма сортировки сегментов, которая сама по себе является простой формой сортировки по основанию).

unsigned char find_first_unique(unsigned char *string)
{
    int chars[256];
    int i=0;
    memset(chars, 0, sizeof(chars));

    while (string[i++])
    {
        chars[string[i]]++;
    }

    i = 0;
    while (string[i++])
    {
        if (chars[string[i]] == 1) return string[i];
    }
    return 0;
}

Answer 9

Ниже приведена реализация Ruby для поиска первого неповторяющегося символа строки:

def first_non_repeated_character(string)
  string1 = string.split('')
  string2 = string.split('')

  string1.each do |let1|
    counter = 0
    string2.each do |let2|
      if let1 == let2
        counter+=1
      end
    end
  if counter == 1 
    return let1
    break
  end
end
end

p first_non_repeated_character('dont doddle in the forest')

А вот реализация JavaScript той же функции стиля:

var first_non_repeated_character = function (string) {
  var string1 = string.split('');
  var string2 = string.split('');

  var single_letters = [];

  for (var i = 0; i < string1.length; i++) {
    var count = 0;
    for (var x = 0; x < string2.length; x++) {
      if (string1[i] == string2[x]) {
        count++
      }
    }
    if (count == 1) {
      return string1[i];
    }
  }
}

console.log(first_non_repeated_character('dont doddle in the forest'));
console.log(first_non_repeated_character('how are you today really?'));

В обоих случаях я использовал счетчик, зная, что если буква нигде не встречается в строке, она будет встречаться в строке только один раз, поэтому я просто считаю ее вхождение.

Answer 10

в рубине:

(Оригинальный кредит: Эндрю А. Смит)

x = "a huge string in which some characters repeat"

def first_unique_character(s)
 s.each_char.detect { |c| s.count(c) == 1 }
end

first_unique_character(x)
=> "u"