爪哇 - 搜索間隔合適的數據結構

Question

可能重複：
Does an open-ended interval implementation exist for Java?

我是新來的Java，我想知道什麼是最好的數據結構，以及如何能我通過該數據結構搜索我的情況： 我有int間隔例如：10-100,200-500,1000-5000和每個間隔我有一個值1,2,3,4。我想知道我怎樣才能保存所有這些間隔和它們的值在數據結構中我怎樣才能通過該數據結構搜索返回特定時間間隔的值。例如，如果我搜索15，也就是在區間10-100，我想返回1

謝謝

Answer 1

我會用這種方法：

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 2

如果你的時間間隔是相互排斥的，使用比較有序映射（java.util.TreeMap中）在間隔的最後一個成員上，並且在搜索的項目的tailMap上使用firstKey應該可以正常工作。

如果間隔可能重疊，則需要一個段樹（http://en.wikipedia.org/wiki/Segment_tree），其中標準庫中沒有實現。

Answer 3

你的問題並不完全清楚，尤其是你的意思是值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" 

Answer 4

使用的HashMap（快，更多的內存）或列表（較慢，很少的內存） 。我爲您提供以下兩種解決方案：

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

使用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); 
    }