使用 Java 有效地将排序的 ArrayList 放入排序的数据结构中并找到小于 x 的数字数量

Question

我有一个已经排序的数组列表。我希望把它放在一个排序的数据结构中，这样我就可以很容易地找到小于指定数量的项目。

到目前为止我是这样做的：

TreeSet<Integer> sortedList = new TreeSet<>(myArrayList); // This is slow

如果我想找到小于或等于 50 的数字的数量（例如），那么我会这样做：

sortedList.headSet(50, true).size(); // This is not that slow

所有这些看起来都非常低效。这主要是因为 myArrayList 已经排序并且初始化 TreeSet 非常慢。

请注意，数组列表很大，查询数量很少（大约10个）。

Answer 1

如果您的 myArrayList 已经排序并且不包含重复项，则二分查找是您的朋友。使用 Collections.binarySearch。 binarySearch returns 现有元素的索引（因此你有 idx+1 个元素小于或等于）或 插入点 给定元素应该在哪里被插入（所以-idx-1是严格少的元素个数，没有相等的元素）。

public static int countLessOrEqual(List<Integer> nums, int limit) {
    int idx = Collections.binarySearch(nums, limit);
    if(idx < 0) return -idx-1;
    return idx+1;
}

用法示例：

List<Integer> nums = Arrays.asList(1, 10, 23, 31, 50, 65, 71, 89, 100);
System.out.println(countLessOrEqual(nums, 50)); // 5
System.out.println(countLessOrEqual(nums, 51)); // 5
System.out.println(countLessOrEqual(nums, 49)); // 4
System.out.println(countLessOrEqual(nums, 0));  // 0
System.out.println(countLessOrEqual(nums, 300)); // 9

如果您的输入列表已排序，但包含重复项，所有重复项都是相邻的，因此您可以对列表进行一次预处理并删除它们（比构建 TreeSet 快得多）：

public static List<Integer> removeAdjacentDuplicates(List<Integer> input) {
    List<Integer> result = new ArrayList<>();
    Integer last = null;
    for(int i=0; i<input.size(); i++) {
        Integer cur = input.get(i);
        if(i == 0 || !cur.equals(last))
            result.add(cur);
        last = cur;
    }
    return result;
}

用法示例：

System.out.println(removeAdjacentDuplicates(
     Arrays.asList(1, 10, 10, 23, 31, 50, 50, 50, 65, 71, 89, 100)));
// [1, 10, 23, 31, 50, 65, 71, 89, 100]

使用 Java 有效地将排序的 ArrayList 放入排序的数据结构中并找到小于 x 的数字数量

Efficiently put sorted ArrayList in sorted data structure and find amount of numbers smaller than x, using Java

java

sorting

tree

data-structures