0

我对 c 中的哈希表实现很新，我正在查看一些面试问题，我发现了一个关于查找数组中元素的奇数出现的问题。我已经完成了所有设置和工作：

int a[256]={0};
char *str="hhlloworldd";
int i;

for(i=0;i<strlen(str);++i)
    a[str[i]]++;

for(i=0;i<strlen(str);i++)
{
    if(a[str[i]]%2 == 1)
    {
        printf("Odd occurrence of %c\n",str[i]);
    }
}

我见过的大多数哈希表解决方案（就数组或字符串等中的元素计数而言）都使用 2 个 for 循环。1 插入任何可能的内容，1 之后检查结果。我相信这仍然是 O(n) 复杂性，因为（如果我错了，请纠正我）但是它通过字符串的 n 次是 O(n) + O(n) 的两倍，这等于 O(n)。我的问题是有没有办法在插入哈希表时检查哈希表以消除第二个 for 循环？

4

3 回答 3

2

关于您的代码有两个观察结果：

  • 它与哈希表无关，因为没有冲突解决方案。
  • 代码的复杂度确实是O(n)，但是你的分析是不正确的：第二次循环的时间是O(256)，换句话说O(1)，对于 的整体复杂度O(n)。
于 2013-02-25T00:08:12.423 回答
1

很多评论：

  • 哈希表不能有冲突。例如，具有完美散列的散列表仍然是散列表。哈希表定义专注于通过哈希函数从键到值的映射（这就是定义）。例如，参见（对于相同的查找数组）：

http://c2.com/cgi/wiki?HashTable

所以上面是一个具有完美哈希函数的哈希表（映射所有元素没有冲突），它将某个元素（一个字符）映射到一个值（出现次数）。

  • 如前所述，strlen 是 Θ(n)，因此每次循环迭代都调用它会导致 Θ(n²)。将 strlen 拉出循环可以解决此问题。

  • 第二个循环是 Θ(n)，但正如已经评论过的那样，如果这个循环通常是 Θ(e)（随着元素的数量而增长），在这种情况下是 Θ(1)，则更有意义。无论如何，请检查原始问题的真正要求。

  • 不可能合并两个循环。这样做的原因是因为只有在处理完字符串中的最后一个元素后才能计算所有数组元素。要明白这一点。如果这不是真的，那么我们可以在更早的时刻得出结论，一些哈希值已经准备好。然后只考虑我们处理最后一个元素之前的那一刻。如果我们还没有处理最后一个元素，那么我们需要将其中的元素增加 1。那么 256 个桶中的任何一个都可能发生变化。但是无法猜测是哪一个，我们需要读取最后一个元素。循环结束后，唯一的出路是再次循环。

于 2013-02-25T01:01:21.090 回答
0

您的代码似乎有错误 - 但也许我没有正确满足您的要求：

如果某个字符 x 在输入中出现奇数次，则第二个 for 循环将在每次看到它时将其报告为“奇数出现”。

您应该将两个 for 循环合并为一个。作为旁注，在循环条件中放置像 strlen() 这样的 O(n) 操作依赖于编译器理解 str 没有被修改，因此 strlen 不会被重复调用，否则最终会得到二次性能。

int a[256]={0};
int n = strlen(str);
int i;

for(i=0;i<n;++i)
{
    ++a[str[i]];
    if(0 != a[str[i]]%2)
    {
        printf("Odd occurrence of %c\n",str[i]);
    }
}

如果密钥空间足够小（在本例中大小为 256）以使一个简单的查找表工作，不确定为什么要使用哈希表。

于 2013-02-25T00:00:35.797 回答