Odnajdywanie pierwszego nie powtarzanego znaku ciągu w O (n) przy użyciu tablicy boolowskiej?

Question

Moje pytanie związane jest z tym wcześniejszym pytaniu

Find the first un-repeated character in a string.

W jednym z moich wywiadów poproszono mnie o napisanie funkcji do określenia pierwszego unikalnego znaku w ciągu znaków w czasie O (n) użycie jako dodatkowej przestrzeni tylko tablicy boolowskiej o długości n. Oznacza to, że znajdź pierwszą nie powtarzającą się literę w łańcuchu, używając tylko złożoności O (n) i tablicy bool o długości n. Czy niektórzy mogą podpowiedzieć, jak rozwiązać ten problem za pomocą tablicy bool?

Answer 1

Mieć dwie tablice logiczne, seenOnce i seenMany. Pętla w ciągu znaków wypełnia tablice. Powtórz pętlę przez ciąg, sprawdzając, czy postać jest widoczna, ale nie jest widoczna. Jeśli jest to twoja pierwsza nie powtarzająca się postać.

Oto przykładowy kod w Pythonie.

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, który nadal wykorzystuje zbyt dużą tablicę boolowską (lub listy python = P). Aby użyć tylko jednej tablicy, możesz mieć jedną tablicę, która podwoi ilość znaków. Zamiast dostępu do drugiej tablicy podwoić indeks i uzyskać dostęp do dużego. Ale to po prostu nieładne.

Nie jestem pewien, czy można to zrobić z mniejszą ilością miejsca.

Answer 2

Dobrze, jeśli rozmiar zestawu znaków jest stała ... Załóżmy na przykład, 0-255 ...

Skanowanie ciąg szuka znaku 0.

Następnie skanuje ciąg patrząc o charakterze 1.

Następnie skanuje ciąg szukasz charakteru 2.

...

Wreszcie, skanowanie ciąg szukasz charakteru 255.

Zajmuje to 256 * n operacji, które są O (n).

Podczas każdego skanu, jeżeli znak jest unikalny, zaznacz jego pozycję w mapie bitowej. Na koniec zwróć postać na pierwszej zaznaczonej pozycji. (Lub po prostu nagraj pierwszy unikalny znak i jego lokalizację za pomocą bitów k + log (n) Użyj twardej tablicy lub czegoś podobnego dla bardzo małych n, w przeciwnym razie, n bitów jest hojny.)

Chociaż jakoś podejrzewam nie o to chodziło rozmawiającemu.

Answer 3

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# implementacja

Answer 4

Dla jednoprzebiegowa Rozwiązanie

Utrzymanie struktury 2 danych:

1. Array/bitmap/hashtable do śledzenia liczby każdego znaku
2. LinkedHashMap aby śledzić postacie, które do tej pory miały miejsce tylko raz.

LinkedHashMap ma

• O (1) dodanie
• O (1) usunięcie

• O (1) wyszukiwania

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

  }

Po przejściu oryginalnego ciągu, szef LinkedHashMap będzie zawierał pierwszy znak, który się nie powtórzy.

Answer 5

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 6

tego w dwóch przejściach:

1. przebieg: tworzenie macierzy bool wielkości 256 i każdego odbarwiającego w tekście oznaczają element Int że wskaźnik (znaki). To zajmuje O (n).

Drugie przejście: dla każdego znaku w tekście sprawdź, czy odpowiedni element tablicy jest zaznaczony. Jeśli nie, to znalazłeś odpowiedź. To również zabiera O (n).