2

我有一个返回整数值或整数范围（initial..final）的方法，我想知道值是否都是不相交的。

有没有比以下更有效的解决方案：

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);
}
4

2 回答 2

4

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

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

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

此外，如果您使用 Set，则可以保证每个值都是唯一的，因此如果您尝试添加一个已经存在的值，add则会返回false. 您可以使用它来稍微简化代码（注意：如果您使用 List，这将不起作用，因为add总是返回trueList）：

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

int value;
if(!list.add(value))
    error("",null);
于 2012-12-10T17:08:08.593 回答
2

涉及范围的问题通常适用于使用树。这是一种使用方法TreeSet：

public class DisjointChecker {

    private final NavigableSet<Integer> integers = new TreeSet<Integer>();

    public boolean check(int value) {
        return integers.add(value);
    }

    public boolean check(int from, int to) {
        NavigableSet<Integer> range = integers.subSet(from, true, to, true);
        if (range.isEmpty()) {
            addRange(from, to);
            return true;
        }
        else {
            return false;
        }
    }

    private void addRange(int from, int to) {
        for (int i = from; i <= to; ++i) {
            integers.add(i);
        }
    }

}

在这里，这些方法不是调用错误处理程序，而是check返回一个布尔值，指示参数是否与所有先前的参数不相交。范围版本的语义与原始代码中的不同；如果范围不是不相交的，则不添加任何元素，而在原始范围内，添加第一个非不相交元素以下的任何元素。

有几点可能需要详细说明：

  • Set::add返回一个布尔值，指示添加是否修改了集合；我们可以将其用作方法的返回值。
  • NavigableSet是一个晦涩但标准的子接口，SortedSet遗憾的是它被忽略了。尽管您实际上可以在此处使用纯SortedSet文本，只需进行少量修改。
  • 该NavigableSet::subSet方法（如SortedSet::subSet）返回限制在给定范围内的基础集的轻量级视图。这提供了一种非常有效的方式来查询树在一次操作中与整个范围的任何重叠。
  • 这里的addRange方法非常简单，当将 m 个项目添加到之前已经查看过 n 个项目的检查器时，运行时间为 O(m log n)。可以通过编写一个SortedSet描述整数范围的实现然后使用来制作一个在 O(m) 中运行的版本Set::addAll，因为TreeSet的实现包含SortedSet在线性时间内添加其他 s 的特殊情况。该特殊集合实现的代码非常简单，但涉及大量样板，因此我将其作为练习留给读者！
于 2012-12-10T18:20:52.583 回答