8

这是一个谷歌面试难题。

问题是找到数组中只出现一次的第一个元素。

例如，abaaacdgadgf给出。我们需要输出b.

简单的解决方案似乎是首先使用哈希表计算每个元素，然后再次循环以获取第一个元素。它将使用 2 个循环。

是否可以仅使用 1 个循环获得结果？

我试图弄清楚，但似乎不可能。

4

5 回答 5

4

哈希表指向链表中的项目。添加项目时，会创建哈希表条目并将指针添加到列表的尾部。当找到重复项时，可以从列表中删除该项目。

仅出现一次的第一个元素将是列表中的第一项。

这段代码有点凌乱，因为大部分代码都是链表实现。

#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;
}
于 2013-07-09T08:56:41.143 回答
2

这是我的解决方案：

每个 'char' 有 4 个可能的统计信息：

  • 1：没见过。
  • 2：看过一个
  • 3：因多次出现而被淘汰。
  • 4：合格

我创建了一个大小为 26 的数组（对于每个 'char'）用于存储 char 的统计信息 合格的元素放在双链表的末尾。

扫描输入数据并根据需要进行所有更新。然后从头到尾扫描列表。第一个非“消除（状态3）”是您的答案。

complexity : n+(26x3) where n = length(dataset)
于 2013-07-09T09:03:24.317 回答
2

是的。在哈希表中，不是维护计数，而是维护遇到元素的第一个索引。还维护一组排序的所有唯一到目前为止的元素，以该索引为键。之后，只需查找排序集中剩余的最小键。

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]
于 2013-07-09T09:04:43.337 回答
1

您可以使用 trie 代替哈希表。如果输入数据与您的哈希函数相冲突，则哈希表将为您提供二次性能。特里对此免疫。

至于另一个循环，我不会太担心。渐近地是相同的复杂度。无论您通过消除循环赢得什么，您都可能会因其余代码的复杂性增加而失败。

于 2013-07-09T12:57:04.610 回答
1

我没有阅读其他答案只是因为我想自己尝试一下。
让我们迭代地改进我们的解决方案。
我们在时间和空间复杂性方面的分析首先需要我们清楚地说明一些事情：
让

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

蛮力算法是遍历字符串，对于字符串的每个元素，我们向右搜索它是否有重复。
时间复杂度：O(N 2 )
空间复杂度：O(1)

我们能做得更好吗？
当然，我们可以遍历字符串并对一个字符出现的次数进行计数。再次遍历字符串以找到第一个计数为 1 的字符。
时间复杂度：O(N+M)
空间复杂度：O(M)

为什么是 O(N+M)？
因为我们需要先将count数组的元素初始化为0。所以即使input是“a”，我们也需要为M个元素初始化count数组。

我们能做得更好吗？
首先让我们向面试官说明这个任务是 Omega(N)，仅仅是因为我们必须看到字符串的每个元素至少一次。通过查看“aaaaaz”的输入实例来实现这一点
所以我们的目标不是提高我们的时间复杂度，只需通过字符串进行一次遍历就可以使实际运行时间更好。
这确实是可能的。

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) 中做到这一点的方法。如果我找到了解决方案，我会更新这个答案。

于 2013-07-09T12:13:48.367 回答