Нахождение первого неповторяющегося символа строки в O (n) с использованием логического массива?

Question

Мой вопрос связан с этим более ранним вопросом

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

В одном из моих интервью меня попросили написать функцию для определения первого уникального символа в строке за время O (n), используя в качестве дополнительного пробела только логический массив длины n. То есть найдите первую неповторяющуюся букву в строке, используя только сложность O (n) и массив bool длины n. Кто-нибудь может подсказать, как решить это с помощью bool array?

Answer 1

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

Сканирование строки в поисках символа 0.

Затем отсканируйте строку в поисках символа 1.

Затем просканируйте строку в поисках символа 2.

...

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

Это занимает 256 * n операций, что равно O (n).

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

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

Answer 2

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

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

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

Answer 3

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;
        }

    }

  }
}

Answer 4

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

Ведение 2 структур данных:

1. Массив / растровое изображение / хеш-таблица для отслеживания количества каждого символа
2. LinkedHashMap для отслеживания символов, которые произошли только один раз.

LinkedHashMap имеет

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

• O (1) search

  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 будет содержатьпервый символ, который не повторяется.

Answer 5

    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());                    
    }

C # реализация

Answer 6

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

Вот пример кода на 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

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

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