java - 在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}

Case 1 : Now when user enters Credits = 50, this range comparator should give answer as

CreditRange :{id:1,credits:0}

Case 2 : Now when user enters Credits = 300, this range comparator should give answer as

CreditRange :{id:4,credits:250}

Case 3 : Now when user enters Credits = 600, this range comparator should give answer as

CreditRange :{id:3,credits:500}

我们可以假设范围数组占用 ~1M 并适合内存。我正在寻找一种简单的算法，它仅使用标准 JDK 集合，不使用任何 3d 方库和特殊数据结构，但运行速度相当快。

你有什么建议？

Answer 1

我猜，这不是你说的范围。相反，您想要小于您传递的元素的最大元素。

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

• 首先实现一个Comparator对于你的类(class)，它根据学分
进行比较
• 然后，使用 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

请重命名您的类(class)。它没有以任何方式描述范围。它或许应该更好地命名为 CreditBound，正如 Jon Skeet 在评论中所指定的那样。