-4

微软面试题

从字符串中删除重复项，不使用 HASHMAP 和 O(n) 时间复杂度

在 O(n 2 ) 时间复杂度上有一个解决方案，但是面试问题特别提到了 NO HASHMAP 和 O(n) 时间。

任何指针都值得赞赏，因为我想不出任何低于 O(n log n) 时间的东西，它采用排序并且确实使用 O(n) 空间。

4

3 回答 3

11

你做了一种桶排序。

  • 创建一个包含每个字符的数组
  • 制作一个包含其对应字符计数的数组

我们使用 2 个这样的数组的唯一原因是因为您明确禁止了哈希映射。你可以随心所欲地表示这个结构。如果允许将 chars 转换为ints，则只需要使用 1 个数组。

由于我们假设可能的字符数量有限，每个数组将是恒定大小，或O(1)

  • 遍历您的字符串，并为您找到count的每个递增。char如果计数已经大于0您找到的重复项。

在您的 char 数组中搜索特定字符需要O(1)时间，因为字符数量有限。

您将执行此搜索 n 次以获得O(n)的净运行时间

如果数组不好，那么您可以创建一个链表来仅保存您找到的值。它仍然是恒定的，因为链表的大小仍然受可能字符数的限制。

如果你这样做，你或多或少会做完全相同的事情，除了它在外观上看起来不像是桶排序策略。

于 2013-06-18T19:14:59.970 回答
3

我可能有另一种解决方案，我认为它更糟糕，但它适用于小字符数组。算法如下：

  1. 我们将每个字母分配给从 2 开始的素数。 - 这将是我们的查找表。
  2. 我们找到所有数字的乘积。-> O(n)
  3. 在循环 -> O(n) 中，我们检查 product % k*k == 0 如果是，我们发现了重复的 k。

此解决方案仅存储 1 个数字，但很容易溢出。不过，主桌会占用很多空间。

编辑：如果我们添加一个只有 40 个唯一字符可用的约束，我们可以使用欧拉二次多项式来找到素数。

P(n) = n*n - n + 41

除了产品之外，这不需要任何额外的空间。

于 2013-06-18T20:00:15.653 回答
0 
traverse the list for i= 0 to n-1 elements
{
  check for sign of A[abs(A[i])] ;
  if positive then
     make it negative by   A[abs(A[i])]=-A[abs(A[i])];
  else  // i.e., A[abs(A[i])] is negative
     this   element (ith element of list) is a repetition
}

您可以轻松地将其修改为数组中的 0。如果是字符，您可以使用其整数代码。

于 2013-06-19T05:01:01.230 回答