java - 在宽范围的整数数组中查找第一个重复元素？

Question

这个问题与Find the first unrepeated character in a string in 其中输入是字符数组有关，我们可以采用大小为 256 的哈希。

但如果，

• 数组中的元素是范围广泛的整数，散列可能非常昂贵。

• 数组包含异构元素、整数或字符，那么哈希如何解决这个问题。

我们可以使用蛮力方法扫描每个元素的整个数组，但在最坏的情况下它需要 O(n²)。

还有其他想法吗？

Answer 1

离线版本：像这样对向量进行排序：

vector<std::pair<int,int> > data;
for (int i=0;i<orignalVec.size();++i)
    data.push_back( make_pair(originalVec[i] , i ) );

然后扫描向量，寻找第一个值相同且位置值最小的一对。这给出了一个O(NlogN)

一个在线版本。使用std::map( O(NlogN)) std::unordered_map( O(N))。

如果数组中的元素是范围很广的整数，散列可能会非常昂贵。

为什么？哈希旨在解决这个问题，不是吗？

如果数组包含异构元素、整数或字符，那么哈希如何解决这个问题。

为这些中的每一个编写不同的哈希函数。对于 , 之类的类型，int我认为 STL 具有内置哈希。floatstd::string

对于元素不支持比较操作的异构容器，hash是我唯一能想到的。

Answer 2

首先按升序或降序对数组进行排序。然后从第二个元素开始循环遍历排序数组，并将每个元素与前一个元素进行比较，看看它们是否匹配。

int[] numbers = {1, 5, 23, 2, 1, 6, 3, 1, 8, 12, 3};
Arrays.sort(numbers);

for (int i = 1; i < numbers.length; i++) {
    if (numbers[i - 1] == numbers[i]) {
        System.out.println("Repeated numbers are : " + numbers[i]);
    }
}