Tìm ký tự không lặp lại đầu tiên của một chuỗi trong O (n) bằng cách sử dụng một mảng boolean?

Question

Câu hỏi của tôi có liên quan đến câu hỏi trước đây

Find the first un-repeated character in a string.

Trong một cuộc phỏng vấn, tôi được yêu cầu viết hàm để xác định ký tự duy nhất đầu tiên trong một chuỗi trong thời gian O (n) sử dụng làm khoảng trống bổ sung chỉ một mảng boolean có độ dài n. Tức là, tìm chữ cái đầu tiên không lặp lại trong một chuỗi chỉ sử dụng độ phức tạp O (n) và một mảng bool có độ dài n. Có thể một số đề nghị làm thế nào để giải quyết nó với mảng bool?

Answer 1

Có hai mảng boolean, được thấyMột lần và đã thấyMany. Vòng lặp qua chuỗi điền các mảng. Lặp lại chuỗi lần nữa để kiểm tra xem ký tự có ở trong chế độ xemĐầu tiên không, nhưng không phải trong phần hiển thị. Nếu đó là ký tự không lặp lại đầu tiên của bạn.

Dưới đây là một số mã ví dụ trong 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 vẫn sử dụng mảng quá boolean (hoặc danh sách python = P). Để chỉ sử dụng một mảng, bạn có thể có một mảng làm tăng gấp đôi số ký tự. Thay vì truy cập vào mảng thứ hai, hãy tăng gấp đôi chỉ mục và truy cập vào chỉ mục lớn. Nhưng đó chỉ là lộn xộn.

Bạn không chắc chắn nó có thể được thực hiện với không gian ít hơn không.

Answer 2

Vâng, nếu kích thước của bộ ký tự là hằng số ... Say, ví dụ, 0-255 ...

Quét chuỗi tìm kiếm nhân vật 0.

Sau đó quét chuỗi tìm kiếm cho nhân vật 1.

Sau đó quét chuỗi tìm kiếm nhân vật 2.

...

Cuối cùng, quét các chuỗi tìm kiếm nhân vật 255.

Thao tác này có 256 * n hoạt động là O (n).

Trong mỗi lần quét, nếu ký tự là duy nhất, hãy đánh dấu vị trí của nó trong bitmap. Cuối cùng trả về ký tự ở vị trí được đánh dấu đầu tiên. (Hoặc chỉ cần ghi lại ký tự đầu tiên và vị trí của nó bằng cách sử dụng bit k + log (n). Sử dụng bảng tra cứu mã hóa cứng hoặc bất kỳ thứ gì cho n rất nhỏ; nếu không, n bit là hào phóng.)

Mặc dù bằng cách nào đó tôi nghi ngờ đây không phải là những gì người phỏng vấn nghĩ đến.

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# thực hiện

Answer 4

Đối với Single Pass Giải pháp

Duy trì cấu trúc 2 dữ liệu:

1. Array/bitmap/Hashtable để theo dõi số lượng của mỗi nhân vật
2. LinkedHashMap để theo dõi các nhân vật đã xảy ra chỉ một lần cho đến nay.

LinkedHashMap có

• O (1) chèn
• O (1) xóa

• O (1) tìm kiếm

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

  }

Sau khi chuỗi gốc được duyệt, đầu của LinkedHashMap sẽ chứa ký tự đầu tiên không được lặp lại.

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

làm điều đó trong hai đèo:

1st pass: tạo mảng bool kích thước 256 và cho mỗi char trong văn bản đánh dấu các yếu tố của chỉ số int (char). Điều này có O (n).

Thẻ thứ hai: cho mỗi char trong văn bản kiểm tra xem phần tử mảng tương ứng có được đánh dấu hay không. Nếu không thì bạn tìm thấy câu trả lời của bạn. Điều này cũng có O (n).