0

问题由两个排序列表组成，没有大小为 n 和 m 的重复项。第一个列表包含应从第二个列表中删除的字符串。

最简单的算法必须进行nxm操作（我相信这个术语是“二次时间”？）。

改进的解决方案是利用两个列表都已排序并在将来的比较中跳过索引低于上次删除索引的字符串这一事实。我想知道那是什么时间复杂度？

这个问题有没有时间复杂度更好的解决方案？

4

4 回答 4

6

你应该看看Merge sort。这就是为什么它有效工作背后的基本思想。

想法是将两个列表一起扫描，这需要O(n+m)时间：

为第一个列表创建一个指针x，比如说，为第二个列表创建A另一个指针。设置和。While和if则添加到新的合并列表并递增。否则添加到新列表并递增。一旦你点击or ，分别从or中获取剩余的元素。yBx=0y=0x < ny < mA[x] < B[y]A[x]xB[y]yx=ny=mBA

于 2012-06-27T20:09:13.743 回答
5

我相信复杂性会是O(n+m)，因为每个列表中的每个项目都会被访问一次。

于 2012-06-27T20:07:16.103 回答
0

计数/桶排序算法将在第二个列表中的每个字符串都是一个桶的情况下工作。

您浏览第二个列表（需要 m 时间）并创建您的存储桶。然后，您浏览您的第一个列表（需要 n 时间）并增加出现次数。然后，您将不得不再次遍历每个存储桶（需要 m 时间），并且只返回出现一次的字符串。Trie 或 HashMap 可以很好地存储桶。应该是 O(n+m+m)。如果您使用 HashSet，则在第二次通过而不是递增计数器时，您会从 Set 中删除。它应该是 O(n+m+(mn))。

于 2012-06-27T22:07:01.550 回答
-1

如果使用二进制搜索，可能是 O(m + log(n)) 吗？

于 2012-06-27T21:55:45.877 回答