-5 java algorithm hashmap data-structures
假设有一大堆范围.例如,大小为5000的集合:
[100,200],[1,59],[3,5],[70,70]...
如何在Java中检查整数n是否有效地落入这些范围中的至少一个？
执行此操作的时间有效方法是Bitset为所有集合中的所有整数创建一个位集.然后,您可以通过一次O(1)通话测试会员资格.
问题是如果整数的组合范围很大,那么Bitset将占用大量内存.
第二种方法是组合重叠范围,并构造一个TreeMap<Integer, Integer>键,其中键是下限,值是每个组合范围的上限.然后使用TreeMap::floorKey和测试找到匹配的范围.此过程是O(logN)其中N是组合的范围的数量.空间使用将是O(N).