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

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

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

使用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

使用此function，您可以确定15的间隔数，即1.您还可以确定数字是否在间隔之间。

编辑：添加示例

  TreeMap map = new TreeMap(); 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 3

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

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

Answer 4

你的问题并不完全清楚，特别是你的意思是值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 5

使用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 intervalMap = new HashMap(); // less memory consuming, little slower List intervalList = new ArrayList(); 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; } }