如何检查整数是否在给定范围的集合中？

假设有一大堆范围.例如,大小为5000的集合:

[100,200],[1,59],[3,5],[70,70]...

如何在Java中检查整数n是否有效地落入这些范围中的至少一个？

执行此操作的时间有效方法是Bitset为所有集合中的所有整数创建一个位集.然后,您可以通过一次O(1)通话测试会员资格.

问题是如果整数的组合范围很大,那么Bitset将占用大量内存.

第二种方法是组合重叠范围,并构造一个TreeMap键,其中键是下限,值是每个组合范围的上限.然后使用TreeMap::floorKey和测试找到匹配的范围.此过程是O(logN)其中N是组合的范围的数量.空间使用将是O(N).