数据结构相关。查找大于或等于给定输入的所有数组元素

Question

我有一长串订单金额，1000、3000、50000、1000000 等

我想找出所有金额大于100000的订单

最简单的解决方案可以遍历整个列表并进行比较，然后将匹配项放入另一个列表，这将为您提供所有数量 > 100000 的列表。

我们是否有任何其他数据结构或算法方法可以更快地解决这个问题？

输入元素的序列无序。

Answer 1

想到的方法可能是保留一个有序的订单列表，然后对限制金额执行二进制搜索。排序列表中该点之前的所有订单都将小于限制金额。

// Generate a random array of numbers
Random r = new Random();
Integer[] numbers = new Integer[r.nextInt(100) + 20];
for (int i = 0; i < numbers.length; i++) {
    numbers[i] = r.nextInt(50000) + 100;
}
// Order the array and print it
Arrays.sort(numbers);
System.out.println(Arrays.toString(numbers));
// Find the index of the amount limit (10000 in this case)
int index = Arrays.binarySearch(numbers, 10000);
// Print the slice of array that is lower than the limit amount
System.out.println(Arrays.toString(Arrays.copyOfRange(numbers, 0, Math.abs(index) + 1)));

Answer 2

有很多数据结构可以给你更好的搜索时间，比如Tree、HashSet ...等等

但是如果您总是希望获得超过 100k 的订单，那么您可以很容易地拥有 2 个列表（一个用于 <100k 的订单，另一个用于 >100k 的订单）。但这对于搜索量始终不变而不是通用解决方案的情况非常具体。

Answer 3

这取决于您要检查订单序列的次数，以及它是否被修改了很多。

如果你只打算这样做一次，简单地遍历整个序列并计数。这将比构建任何其他数据结构更快，因为无论如何您都必须检查所有订单。

此外，遍历一百万个项目的列表将非常快，即使您重复这样做也是如此。您确定这里有性能问题吗？

数据结构相关。查找大于或等于给定输入的所有数组元素

Datastructure related. Find all arrays elements greater than or equal to given input

java

algorithm

graph-algorithm

data-structures