<分区>
这是一个 Google 面试难题。
问题是找到数组中第一个只出现一次的元素。
例如,给出了abaaacdgadgf
。我们需要输出b
。
简单的解决方案似乎是首先使用哈希表对每个元素进行计数,然后再次循环以获取第一个元素。它将使用 2 个循环。
是否可以只使用 1 个循环得到结果?
我想弄明白,但似乎不可能。
标签 algorithm
<分区>
这是一个 Google 面试难题。
问题是找到数组中第一个只出现一次的元素。
例如,给出了abaaacdgadgf
。我们需要输出b
。
简单的解决方案似乎是首先使用哈希表对每个元素进行计数,然后再次循环以获取第一个元素。它将使用 2 个循环。
是否可以只使用 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;
}
关于algorithm - 找到第一个只出现一次的元素,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17543859/