查找值在Java中的范围

Question

假设,我有一个未排序的范围数组.例如

class CreditRange{
   long credits;
   int id;
}

现在我想找到,给定信用计数值属于CreditRange中的哪一个.

可能Set<CreditRange>的值可以

CreditRange :{id:1,credits:0}
CreditRange :{id:2,credits:100}
CreditRange :{id:3,credits:500}
CreditRange :{id:4,credits:250}

情况1:现在当用户输入Credits = 50时,此范围比较器应给出答案为

CreditRange :{id:1,credits:0}

情况2:现在当用户输入Credits = 300时,此范围比较器应给出答案为

CreditRange :{id:4,credits:250}

情况3:现在当用户输入Credits = 600时,此范围比较器应给出答案为

CreditRange :{id:3,credits:500}

我们可以假设范围数组需要大约1M并且适合内存.我正在寻找一种简单的算法,它只使用标准的JDK集合,没有任何3d派对库和特殊的数据结构,但工作速度相当快.

你会建议什么？

Answer 1

我想,这不是你所说的范围.相反,您希望最小元素小于传递的元素.

您可以按照以下步骤解决问题:

• 首先Comparator为您的班级实施一个,根据学分进行比较
• 然后,使用a TreeSet,将该比较器的实例传递给它的构造函数.根据比较器,它将对其中的项进行排序.
• 然后根据比较器使用TreeSet#floor(E)方法得到小于的最大元素E.当然,您必须创建一个CreditRange搜索对象.你不能只搜索300.

演示代码:

NavigableSet<Integer> set = new TreeSet<>();
set.add(0);   set.add(100);
set.add(250); set.add(500);

System.out.println(set.floor(50));  // 0
System.out.println(set.floor(300)); // 250

请重命名你的课程.它没有以任何方式描绘范围.它应该更好地命名为CreditBoundJon Skeet在评论中指定的.