Найти первый элемент, который встречается только один раз

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 

Brute алгоритм силы, чтобы пересечь строку и для каждого элемента строки мы ищем для его чтобы увидеть, есть ли у него дубликат.
Время Сложность: O (N 2 )
Space Сложность: O (1)

Можем ли мы сделать лучше?
Конечно, мы можем пройти через строку и сделать подсчет много раз персонаж appears.Make другой обход через строку, чтобы найти первый символ, который имеет подсчитывать 1.
Временная сложность: O (N + M)
Space Сложность : O (M)

Почему это O (N + M)?
Поскольку нам нужно сначала инициализировать элементы массива count. Так же, даже если ввод «a», нам нужно инициализировать массив count для M элементов.

Можем ли мы сделать лучше?
Сначала давайте заявим интервьюеру, что эта задача - Омега (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)
Space Сложность: O (M)

Можем ли мы сделать лучше?

Можем ли мы сделать это в O (N), возможно?
Я все еще думаю о способе сделать это в истинном O (N) .IF Я нахожу решение, я обновлю этот ответ.

Answer 5

Вместо хеш-таблицы вы можете использовать trie. Если входные данные замышляют против вашей хеш-функции, хэш-таблица получит квадратичную производительность. Трое невосприимчиво к этому.

Что касается другого цикла, я бы не стал слишком беспокоиться об этом. Это такая же сложность асимптотически. Независимо от того, что вы выиграете, устраняя цикл, вы, вероятно, проиграете в увеличенной сложности остальной части кода.