java - 在未排序的字符串数组中查找重复项 - O(nlogn)

Question

我得到了字符串哈希值数组，例如：“123-51s-12as-dasd1-das-41c-sadasdgt-31”。我需要找出是否有任何重复。问题是，我需要在 O(nlogn) 中找到它们。

1）我的想法：

为此，我可以使用二进制搜索算法。但二分查找仅适用于已排序的数值数组。所以我问：有没有办法对字符串数组进行排序？

2）我愿意接受任何其他答案。我的问题是： 如何在未知字符串数组中找到所有重复项 - nlogn。

Answer 1

由于时间限制是nlog(n)，您可以安全地首先对数组进行排序，然后从左到右进行扫描以检查重复的字符串。

Answer 2

您可以使用 aSet<String>并通过循环数组将字符串插入其中：遍历数组是 O(n)，插入是 O(log(n))。如果.add()返回 false，这是重复的：

public Set<String> getDups(String[] hashes)
{
    Set<String> all = new HashSet<String>();
    Set<String> ret = new HashSet<String>();
    for (final String hash: hashes)
        if (!all.add(hash)) // already seen
            ret.add(hash);
    return ret;
}