7

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

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 方库和特殊数据结构，但运行速度相当快。

你有什么建议？

4

2 回答 2

9

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

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

  • 首先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

请重命名您的班级。它没有以任何方式描述范围。CreditBound按照 Jon Skeet 在评论中指定的名称，它也许应该更好地命名。

于 2013-09-28T08:08:00.750 回答
2

正如 Rohit 所提到的，一种简单的方法是使用 TreeSet floor（另一种是实现二进制搜索的修改变体。这是一个更完整的答案：

package test;

import java.util.TreeSet;

class CreditRange implements Comparable<CreditRange> {
  long credits;
  int id;

  public CreditRange(int id, long credits) {
    this.id = id;
    this.credits = credits;
  }

  public CreditRange(long credits) {
    this.id = -1;
    this.credits = credits;
  }

  @Override
  public int compareTo(CreditRange o) {
    return credits < o.credits ? -1 : credits > o.credits ? 1 : 0;
  }

  @Override
  public String toString() {
    return "id:" + id + ", credits:" + credits;
  }
}

public class Test {
  public static void main(String[] args) {
    TreeSet<CreditRange> set = new TreeSet<>();
    set.add(new CreditRange(1, 0));
    set.add(new CreditRange(2, 100));
    set.add(new CreditRange(3, 500));
    set.add(new CreditRange(4, 250));
    System.out.println(set.floor(new CreditRange(50)));
    System.out.println(set.floor(new CreditRange(300)));
    System.out.println(set.floor(new CreditRange(600)));
  }
}
于 2013-09-28T08:44:49.310 回答