我正在寻找一种更快的方法来查找元素数组是否仅包含不同的元素.最糟糕的事情是采用每个元素并将其与数组中的每个其他元素进行比较.接下来最好的方法是对列表进行排序,然后进行比较,但仍然没有提高这一点.有没有其他方法可以做到这一点？
Duk*_*ing 23
蛮力:
蛮力(用每个其他元素检查每个元素)都需要.O(n2)
排序:
排序采用O(n log n),通常被认为是相当不错的运行时间.
排序具有高于以下(哈希表)方法的优点,因为它可以就地完成(O(1)额外空间),其中 - 因为下面需要O(n)额外的空间.
哈希表:
另一种方法是使用哈希表.
对于每个项目:
由于insert和contains包含在O(1)哈希表上预期运行的查询,因此可以预期总运行时间O(n),并且如上所述,O(n)还有额外的空间.
位数组:
另一种替代方案是,如果元素在某个给定范围内都是整数,则具有大小等于整数范围的位数组.
与哈希表方法的操作类似,对于每个元素,您将检查是否设置了适用位,然后进行设置.
这需要O(m + n)时间和O(m)额外的空间,其中m是整数的范围,并且n是数组的大小(除非您考虑将数组分配为空闲,在这种情况下,它只需要O(n)时间).
| 归档时间： |
|
| 查看次数： |
17434 次 |
| 最近记录： |