0

最近在一次采访中被问到这个问题。我在 O(n) 时间内给出了答案，但分两次。他还问我如果 url 列表无法放入内存中该怎么做。很感谢任何形式的帮助。

4

5 回答 5

6

如果这一切都适合内存，那么问题很简单：创建两个集合（选择您喜欢的数据结构），最初都是空的。一个将包含唯一的 URL，另一个将包含多次出现的 URL。扫描一次 URL 列表。对于每一个URL，如果存在于唯一集中，则将其从唯一集中移出，放入多重集中；否则，如果它不存在于多重集中，则将其添加到唯一集中。

如果该集合不适合内存，则问题很困难。O(n) 的要求并不难满足，但“单次通过”的要求（似乎排除了随机访问等）是困难的；我认为如果没有对数据的一些限制，这是不可能的。您可以使用对集合有大小限制的集合方法，但这很容易被不幸的数据排序所破坏，并且无论如何只有一定的概率（<100％）找到一个唯一元素（如果存在）。

编辑：

如果您可以设计一个存在于大容量存储中的集合数据结构（因此它可以大于内存中的容量）并且可以在 O(1)（摊销）时间内进行查找、插入和删除，那么您可以使用它用第一种方法解决第二个问题的结构。也许面试官所寻找的只是将 URL 转储到具有 URL 唯一索引和计数列的数据库中。

于 2012-07-01T05:47:15.027 回答
2

可以尝试使用 Trie 结构来保存数据。它被压缩了，所以它会占用更少的内存，作为常见 url 部分的内存重用。

循环看起来像：

add string s to trie;
check that added string is not finished in existing node
    internal node -> compress path
    leaf node -> delete path
于 2012-07-01T06:52:59.287 回答
0

对于“适合内存”的情况，您可以使用如下两个哈希表（伪代码）：

hash-table uniqueTable = <initialization>;
hash-table nonUniqueTable = <initialization>;
for-each url in url-list {
    if (nonUniqueTable.contains(url)) {
        continue;
    }
    else if (uniqueTable.contains(url)) {
        nonUniqueTable.add(url);
        uniqueTable.remove(url);
    }
    else {
        uniqueTable.add(url)
    }
}
if (uniqueTable.size() > 1)
    return uniqueTable.first();
于 2012-07-01T05:46:57.103 回答
0

基于 Python

你有一个list- 不确定它“来自”哪里，但如果你已经在内存中拥有它，那么：

L.sort()
from itertools import groupby
for key, vals in groupby(L, lambda L: L):
    if len(vals) == 1:
       print key

否则使用存储（可能使用）：

import sqlite3
db = sqlite3.connect('somefile')
db.execute('create table whatever(key)')

将您的数据放入其中，然后执行“select * from any group by key where count(*) = 1)”

于 2012-07-01T06:26:15.010 回答
-1

这实际上是一个经典的面试问题，他们期望的答案是您首先对 url 进行排序，然后进行二分搜索。如果它不适合内存，您可以对文件执行相同的操作。

于 2012-07-01T06:31:46.737 回答