java - 高效搜索非空交集(Java)

Question

我有一个返回整数值或整数范围(初始..最终)的方法，我想知道值是否都是不相交的。

有没有比下面这个更有效的解决方案:

ArrayList<Integer> list = new ArrayList<Integer>();

// For single value
int value;
if(!list.contains(value))
    list.add(value);
else
    error("",null);

// Range
int initialValue,finalValue;
for(int i = initialValue; i <= finalValue; i++){
    if(!list.contains(i))
        list.add(i);
    else
        error("",null);
}

Answer 1

在 HashSet 中查找值(包含)平均而言，它是一个恒定时间操作 (O(1))，优于 List，其中 contains 是线性的 (O(n))。因此，如果您的列表足够大，可能值得将第一行替换为:

HashSet<Integer> list = new HashSet<Integer>();

这样做的原因是，要在(未排序的)列表中查找值，您需要检查列表中的每个索引，直到找到您想要的索引或用完要检查的索引。平均而言，如果值在列表中，您将在查找值之前检查一半列表，如果不在列表中，则检查整个列表。对于 hash table ，您根据要查找的值生成一个索引，然后检查该索引(您可能需要 check more than one ，但在设计良好的哈希表中应该不常见)。

此外，如果您使用 Set，则可以保证每个值都是唯一的，因此如果您尝试 add a value that already exists, add will return false .您可以使用它来稍微简化代码(注意:如果您使用列表，这将不起作用，因为 add always returns true on a List ):

HashSet<Integer> list = new HashSet<Integer>();

int value;
if(!list.add(value))
    error("",null);