查找数组中所有元素是否都不同的最快方法？ [英] fastest way to find if all the elements of an array are distinct?

问题描述

我正在寻找一种更快的方法来查找元素数组是否仅包含不同的元素。最糟糕的事情是获取每个元素并将其与数组中的每个其他元素进行比较。下一个最好的方法是对列表进行排序，然后进行比较，但这仍然没有太大的改进。还有其他方法吗？

解决方案

蛮力：

蛮力（将每个元素与其他元素进行检查）需要 O（n 2 ）。 / p>

排序：

排序需要 O（n log n），通常被认为是相当不错的运行时间。

排序在以下情况（哈希表）中具有优势它可以就地完成（ O（1）多余的空间），其中-如下所示需要 O（n）多余的空间。

哈希表：

另一种方法是使用哈希表。

对于每个项目：

• 检查哈希表中是否存在该项目（如果存在，则所有项目都不不同），


• 将该项目插入哈希表中

由于插入了nd包含在哈希表上的预期 O（1）中运行的查询，整体运行时间预计为 O（n），以及如上所述， O（n）多余的空间。

位数组：

如果元素都是给定范围内的所有整数，则另一种替代方法是使用位数组，其大小等于整数范围。

对于哈希表方法，每个元素，请检查是否设置了适用的位，然后进行设置。

这需要 O（m + n）时间和 O（m）多余的空间，其中<​​code> m 是整数范围，而 n 是数组的大小（除非您考虑将数组分配为自由数组，在这种情况下，它只需要 O（n）时间）。

I am looking for a faster way to find whether an array of elements contains distinct elements only. The worst thing to do is to take each element and compare it to every other element in the array. Next best would be to sort the list and then compare, which still does not improves this much. Is there any other way to do this?

解决方案

Brute-force:

Brute-force (checking every element with every other element) takes O(n2).

Sorting:

Sorting takes O(n log n), which is generally considered to be a fairly decent running time.

Sorting has the advantage above the below (hash table) approach in that it can be done in-place (O(1) extra space), where-as the below takes O(n) extra space.

Hash table:

An alternative is to use a hash table.

For each item:

• Check if that item exists in the hash table (if it does, all items are not distinct) and
• Insert that item into the hash table

Since insert and contains queries run in expected O(1) on a hash table, the overall running time would be expected O(n), and, as mentioned above, O(n) extra space.

Bit array:

Another alternative, if the elements are all integers in some given range, is to have a bit array with size equal to the range of integers.

Similarly to what was done for the hash table approach, for each element, you'd check whether the applicable bit is set, and then set it.

This takes O(m + n) time and O(m) extra space where m is the range of integers and n is the size of the array (unless you consider allocating the array to be free, in which case it just takes O(n) time).

这篇关于查找数组中所有元素是否都不同的最快方法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！