java - Java - 适合搜索区间的数据结构

Question

可能重复：
Java 是否存在开放式区间实现？

我是 Java 新手，我想知道什么是最好的数据结构，以及如何针对我的情况搜索该数据结构：我有 int 间隔，例如：10-100、200-500、1000-5000 和每个区间我都有一个值 1、2、3、4。我想知道如何将所有这些区间及其值保存在数据结构中，以及如何搜索该数据结构以返回特定区间的值. 例如。如果我搜索 15，即间隔 10-100，我想返回 1。

谢谢

Answer 1

使用 TreeMap，它是 NavigableMap（Java 6 或更高版本）。

假设您有条目key->value (10->1, 100->1, 200->2, 500->2, 1000->3, 5000->3)

floorEntry(15)将返回10->1

ceilingEntry(15)将返回100->1

有了这个，您可以确定 15 的区间数，即 1。您还可以确定一个数字是否在区间之间。

编辑：添加示例

    TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
    map.put(10, 1);
    map.put(100, 1);
    map.put(200, 2);
    map.put(500, 2);
    map.put(1000, 3);
    map.put(5000, 3);
    int lookingFor = 15;
    int groupBelow = map.floorEntry(lookingFor).getValue();
    int groupAbove = map.ceilingEntry(lookingFor).getValue();
    if (groupBelow == groupAbove) {
        System.out.println("Number " + lookingFor + " is in group " + groupBelow);
    } else {
        System.out.println("Number " + lookingFor + 
                " is between groups " + groupBelow + " and " + groupAbove);
    }

Answer 2

如果您的间隔是互斥的，则在间隔的最后一个成员上使用比较器并在搜索项目的 tailMap 上使用 firstKey 的排序映射 (java.util.TreeMap) 应该可以正常工作。

如果间隔可能重叠，您需要一个分段树 (http://en.wikipedia.org/wiki/Segment_tree)，标准库中没有实现。

Answer 3

我会使用这种方法：

import static org.hamcrest.core.Is.is;
import static org.junit.Assert.assertThat;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

public class IntervalsTest {


    @Test
    public void shouldReturn1() {
        Intervals intervals = new Intervals();

        intervals.add(1, 10, 100);
        intervals.add(2, 200, 500);

        int result = intervals.findInterval(15);

        assertThat(result, is(1));

    }

    @Test
    public void shouldReturn2() {
        Intervals intervals = new Intervals();

        intervals.add(1, 10, 100);
        intervals.add(2, 200, 500);

        int result = intervals.findInterval(201);

        assertThat(result, is(2));

    }
}

class Range {

    private final int value;

    private final int lowerBound;

    private final int upperBound;


    Range(int value, int lowerBound, int upperBound) {
        this.value = value;
        this.lowerBound = lowerBound;
        this.upperBound = upperBound;
    }

    boolean includes(int givenValue) {
        return givenValue >= lowerBound && givenValue <= upperBound;

    }

    public int getValue() {
        return value;
    }
}

class Intervals {

    public List<Range> ranges = new ArrayList<Range>();

    void add(int value, int lowerBound, int upperBound) {
        add(new Range(value, lowerBound, upperBound));
    }

    void add(Range range) {
        this.ranges.add(range);
    }

    int findInterval(int givenValue) {
        for (Range range : ranges) {
            if(range.includes(givenValue)){
                return range.getValue();
            }
        }

        return 0; // nothing found // or exception
    }
}

Answer 4

使用 hashmap（快，更多内存）或 List（更慢，更少内存）。我为您提供以下两种解决方案：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Interval {

    private int begin;
    private int end;
    // 1, 2, 3, 4
    private int value;

    public Interval(int begin, int end, int value) {
        this.begin = begin;
        this.end = end;
        this.value = value;
    }

    public int getBegin() {
        return begin;
    }

    public void setBegin(int begin) {
        this.begin = begin;
    }

    public int getEnd() {
        return end;
    }

    public void setEnd(int end) {
        this.end = end;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public boolean contains(int number) {
        return (number > begin - 1) && (number < end + 1);
    }
}

public class IntervalSearch {

    // more memory consuming struct, fastest
    Map<Integer, Interval> intervalMap = new HashMap<Integer, Interval>();

    // less memory consuming, little slower
    List<Interval> intervalList = new ArrayList<Interval>();

    private boolean fastMethod = true;

    public IntervalSearch(boolean useFastMethod) {
        this.fastMethod = useFastMethod;
    }

    public Integer search(int number) {
        return fastMethod ? searchFast(number) : searchSlow(number);
    }

    private Integer searchFast(int number) {
        return intervalMap.get(number).getValue();
    }

    private Integer searchSlow(int number) {
        for (Interval ivl : intervalList) {
            if (ivl.contains(number)) {
                return ivl.getValue();
            }
        }
        return null;
    }

    public void addInterval(Integer begin, Integer end, Integer value) {
        Interval newIvl = new Interval(begin, end, value);
        if (fastMethod) {
            addIntervalToMap(newIvl);
        } else {
            addIntervalToList(newIvl);
        }
    }

    private void addIntervalToList(Interval newIvl) {
        intervalList.add(newIvl);
    }

    private void addIntervalToMap(Interval newIvl) {
        for (int i = newIvl.getBegin(); i < newIvl.getEnd() + 1; i++) {
            intervalMap.put(i, newIvl);
        }
    }

    public boolean isFastMethod() {
        return fastMethod;
    }
}

Answer 5

您的问题并不完全清楚，尤其是值 1、2、3、4 是什么意思。但是，如果您想要一个包含区间限制的数据结构，并检查其中是否有数字，那就做一个！像这样：

public class Interval {
    int low;
    int high;

    public Interval(int low, int high) {
        this.low = low;
        this.high = high;
    }

    public boolean intervalContains(int value) {
        return ((value >= low) && (value <= high));
    }
}

并使用它：

Interval theInterval = new Interval(10,100);
System.out.print(theInterval.contains(15)); // prints "true"