7

重複の可能性：
Javaにはオープンエンドのインターバル実装が存在しますか？

私はJavaを初めて使用しますが、最適なデータ構造とは何か、およびそのデータ構造を検索して自分のケースを検索する方法を知りたいです。int間隔があります（例：10-100、200-500、1000-5000）。各間隔の値は1、2、3、4です。これらすべての間隔とその値をデータ構造に保存する方法と、そのデータ構造を検索して特定の間隔の値を返す方法を知りたいです。 。例えば。15を検索する場合、つまり間隔10〜100の場合、1を返します。

ありがとうございました

4

5 に答える 5

9

NavigableMap（Java 6以降）であるTreeMapを使用します。

エントリがあるとします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);
    }
于 2012-12-06T12:11:22.697 に答える
3

間隔が相互に排他的である場合、間隔の最後のメンバーでコンパレータを使用し、検索されたアイテムのtailMapでfirstKeyを使用するソートされたマップ（java.util.TreeMap）は正常に機能するはずです。

間隔が重なる可能性がある場合は、セグメントツリー（http://en.wikipedia.org/wiki/Segment_tree）が必要ですが、標準ライブラリには実装されていません。

于 2012-12-06T11:28:44.390 に答える
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
    }
}
于 2012-12-06T11:38:53.613 に答える
2

ハッシュマップ（高速でメモリが多い）またはリスト（低速でメモリが少ない）を使用します。以下に両方のソリューションを提供します。

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;
    }
}
于 2012-12-06T11:52:58.277 に答える
1

質問は完全には明確ではありません。特に、値1、2、3、4の意味は明確ではありません。ただし、間隔の制限を保持し、その範囲内に数値があるかどうかを確認するデータ構造が必要な場合は、1つ作成してください。このような：

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"
于 2012-12-06T11:32:19.630 に答える