Java - 适用于搜索间隔的数据结构

Question

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

我是Java的新手,我想知道什么是最好的数据结构,我如何在我的情况下搜索数据结构:我有int间隔,例如:10-100,200-500,1000-5000和for每个区间我有一个值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

我会使用这种方法：

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