查找僅出現一次的第一個元素

Question

這是一個Google面試難題。

問題是要找到只發生一次的數組中的第一個元素。例如，abaaacdgadgf被給出。我們需要輸出b。

簡單的解決方案似乎是先使用散列表對每個元素進行計數，然後再次循環以獲取第一個元素。它將使用2個循環。

是否有可能得到的結果只使用1循環？

我試圖弄明白，但似乎不可能。

Answer 1

哈希表指向鏈接列表中的項目。添加項目時，創建哈希表條目並將指針添加到列表的尾部。當找到重複項目時，該項目可以從列表中刪除。

第一個只出現一次的元素將成爲列表中的第一項。

這段代碼有點不整齊，因爲大部分代碼都是鏈表實現。

#include <stdio.h> 
#include <stdlib.h> 
#include <limits.h> 

typedef struct stLISTITEM 
{ 
    char data; 
    struct stLISTITEM* previous; 
    struct stLISTITEM* next; 
} LISTITEM; 

char firstCharThatOccursOnce(const char* s) { 
    char ret; 
    LISTITEM* head; 
    LISTITEM* tail; 
    LISTITEM* table[CHAR_MAX + 1] = {NULL}; /* Just pretend this is a hash table please */ 
    LISTITEM* cur; 
    int i; 

    head = malloc(sizeof(*head)); 
    tail = malloc(sizeof(*tail)); 

    head->next = tail; 
    tail->previous = head; 
    tail->data = '\0'; /* If all characters are repeated then return NULL character */ 

    for (; *s; s++) { 
     cur = table[*s]; 

     if (cur == NULL) { 
      /* Item hasn't been seen before */ 

      cur = malloc(sizeof(*cur)); 
      cur->data = *s; 

      /* Add it to the end of the list */ 
      tail->previous->next = cur; 
      cur->previous = tail->previous; 
      tail->previous = cur; 
      cur->next = tail; 

      /* Add it to the table */ 
      table[*s] = cur; 
     } 
     else if (cur->next == NULL) { 
      /* Seen it before, but already removed */ 
     } 
     else { 
      /* Seen it before, remove from list */ 
      cur->previous->next = cur->next; 
      cur->next->previous = cur->previous; 

      cur->next = NULL; 
      cur->previous = NULL; 
     } 
    } 

    ret = head->next->data; 

    for (i = 0; i <= CHAR_MAX; i++) { 
     free(table[i]); 
    } 

    free(head); 
    free(tail); 

    return ret; 
} 

int main(int argc, char const *argv[]) 
{ 
    char result = firstCharThatOccursOnce("abaaacdgadgf"); 

    printf("'%c' (%i)\n", result, result); 

    return 0; 
} 

Answer 2

這裏我的解決辦法：

每個 '字符' 有4個統計可能：

• 1：從來沒見過。
• 2：看過一個
• 3：因多次出現而被淘汰。
• 4：合格

創建尺寸26的用於存儲字符 合格元件在雙鏈表的末尾放置的統計信息的陣列（每個「字符」）。

掃描輸入數據並根據需要進行所有更新。 然後從頭到尾掃描列表。第一個未消除（狀態3）' 是您的答案。

complexity : n+(26x3) where n = length(dataset) 

Answer 3

是的。在散列表中，不是維護計數，而是維護遇到元素的第一個索引。還維護一組有序的所有獨一無二的元素，並以該索引爲關鍵字。之後，只需查找排序集中剩餘的最小密鑰即可。

encountered = dict() 
unique = sorted_set() 

for i in range(len(A)): 
    elem = A[i] 
    if elem in encountered: 
     first_index = encountered[elem] 
     del unique[first_index] 
    else: 
     unique[i] = elem 
     encountered[elem] = i 

min_index = unique.keys()[0] 
first_unique_elem = A[min_index] 

Answer 4

我還沒有閱讀其他答案，只是因爲我想給它一個自己去。
讓我們反覆改進我們的解決方案。
我們在時間和空間複雜度分析，需要我們顯然處於第一狀態的幾件事情：
讓

N = length of string 
M = numbers of characters in alphabet 

窮舉算法是遍歷字符串，字符串中的每個元素，我們搜索到它有權查看它是否有重複。
時間複雜度：O（N ）
空間複雜度：O（1）

我們可以做得更好？
當然，我們可以遍歷字符串，並多次字符通過串地發現，具有第一個字符appears.Make另一個穿越數計數1
時間複雜度：O（N + M）
空間複雜：O（M）

爲什麼這是O（N + M）？
因爲我們需要首先將count數組的元素初始化爲0。即使輸入是「a」，我們也需要初始化M個元素的count數組。

我們可以做得更好嗎？
首先讓我們向訪問者說明這個任務是Omega（N），只是因爲我們必須看到每個元素的字符串至少一次。通過查看「aaaaaaz」的輸入實例來實現這一點
因此，我們不是瞄準更好地減少時間複雜度，只需在字符串中穿過一個遍歷即可簡化實際運行時間。
這確實是可能的。

for(int i=0;i<N;i++) 
{ 
    if(visited[i]==-2)continue; 
    if(visited[i]==-1)visited[i]=i;continue; 
    visited[i]=-1; 
} 
int F=N; 
char res=' '; 
for(int i=0;i<M;i++) 
{ 
    if(visited[i]>=0) 
    { 
    F=min(F,visited[i]); 
    res=A[visited[i]]; 
    } 
} 
return res; 

時間複雜度：O（N + M）
空間複雜度：O（M）

我們可以做得更好？

我們可以在O（N）中做這個嗎？
我仍然想着在真正的O（N）.IF中做到這一點的方法。我打了一個解決方案，我會更新這個答案。

Answer 5

您可以使用trie來代替散列表。如果輸入數據與你的散列函數共同作用，散列表會讓你獲得二次性能。這一點對此是免疫的。

至於另一個循環，我不會擔心它太多。漸進式複雜性是一樣的。無論您通過消除循環贏得了什麼，您可能會因代碼其餘部分的複雜性增加而失敗。