找到仅出现一次的第一个元素

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