Поиск первого не повторяющегося символа строки в O (n) с использованием булевого массива?

Ответ 1

Ну, если размер набора символов является постоянным... Скажем, например, 0-255...

Сканировать строку, ищущую символ 0.

Затем сканируйте строку, которая ищет символ 1.

Затем сканируйте строку, которая ищет символ 2.

...

Наконец, сканируйте строку, которая ищет символ 255.

Это занимает 256 * n операций, которые являются O (n).

Во время каждого сканирования, если символ уникален, отметьте его положение в растровом изображении. В конце верните символ в первую отмеченную позицию. (Или просто записать первый уникальный символ и его местоположение с помощью бит k + log (n). Используйте жестко закодированную таблицу поиска или что угодно для очень маленького n, в противном случае n бит великодушны.)

Хотя почему-то я подозреваю, что это не то, что имел в виду интервьюер.

Ответ 2

    private static void FirstNonRepeatingCharacters()
    {
        string s = "abbazccdde";
        var result = from item in s
                     group item by item into groupedItems
                     where groupedItems.Count() == 1
                     select groupedItems.Key;
        Console.WriteLine(result.First());                    
    }

Реализация С#

Ответ 3

Для решения с одним проходом

Поддерживать 2 структуры данных:

• Array/bitmap/hashtable для отслеживания количества символов
• LinkedHashMap для отслеживания символов, которые произошли только один раз.

LinkedHashMap имеет

• O (1) вставка
• O (1) удаление

• O (1) поиск

  class Node
  {
    char data;
    Node next;
    Node prev;
  };
  
  class LinkedHashMap
  {
          // This will keep the insertion order intact
          Node listHead;
          Node currentTail = listHead;
          HashTable<char, Node> charExistsMap;
  
      void Add(char ch) 
      {
          if(!charExistsMap.ContainsKey(ch)) 
          {
              // Add to both hashtable and linkedlist
              Node n = new Node(ch);
              n->next = null;
              n->prev = curentTail; // Added To List
              currentTail = n;
              charExistMap.Add(ch, n);
          }
          else 
          {
              // Remove from both hashtable and linkedlist
              Node n = charExistMap.Remove(ch);
              if(n->prev != null) 
              {
                  n->prev->next = n->next
                  listHead = n->next; // update head
              }
              if(n->next != null)
                  n->next->prev = n->prev;
           }
      }
  
      char GetFirstNonRepeatingChar()
      {
          return listHead->data;
      }
  

  }

После прохождения исходной строки глава LinkedHashMap будет содержать первый символ, который не повторяется.

Ответ 4

public class FirstUniqueChar {

  public static void main(String[] args) {

    String test = "ABxacd";

    test = test.toUpperCase();
    for (int i = 0; i < test.length(); i++) {
        int firstIndex = test.indexOf(test.charAt(i));
        int lastIndex = test.lastIndexOf(test.charAt(i));
        if (firstIndex == lastIndex) {
            System.out.println("First unique char of String " + test.charAt(i));
            break;
        }

    }

  }
}

Ответ 5

Сделайте это за два прохода:

1-й проход: создайте массив bool размером 256 и для каждого char в текстовой пометке элемент index int (который char). Это берет O (n).

2-й проход: для каждого char в тексте проверьте, отмечен ли соответствующий элемент массива. Если нет, тогда вы нашли свой ответ. Это также принимает O (n).

Ответ 6

Имейте два булевых массива, увиденных и увиденных. Цикл по строке заполняет массивы. Перебирайте строку, снова проверяя, присутствует ли символ вначале, но не отображается много. Если это ваш первый неповторяющийся символ.

Вот пример кода в python.

subject = "ttojxxlma"

seenOnce = [False for i in range(256)]
seenMany = [False for i in range(256)]

for c in subject:
    index = ord(c)
    if seenOnce[index] == False:
        seenOnce[index] = True
    else:
        seenMany[index] = True

for c in subject:
    index = ord(c)
    if seenOnce[index]==True and seenMany[index] != True:
        print(c)
        break

Хорошо, что все еще использует слишком логический массив (или списки python = P). Чтобы использовать только один массив, у вас может быть один массив, который удваивает количество символов. Вместо доступа к второму массиву удвоить индекс и получить доступ к большому. Но это просто грязно.

Не уверен, что это можно сделать с меньшим объемом.