求一查找区间的算法

0 0

求一查找区间的算法25

给定一组区间(有重叠)，如A0=[1-3000],A1=[10-20],A2=[30-100],A3=[50-150]……An-2=[1500-1700],An-1=[1800-1850],An=[1900-2000],An+1=[2800-3000]……求一种快速查找某个数所在的区间的算法，如查找2500的结果为A0，求特各路大神不吝赐，小弟感激不尽...

问题补充：哦，忘了说了，如果是有多个区间的话取区间间隔最小的，如15的话，输出A1

数据结构算法区间

2013年5月28日 11:08

忆~ling
5
0 0 4

5个答案按时间排序按投票排序

0 0

思路将结束区间的值作为一个key,value为该区间的的范围，排好序之后，根据传进来的数据大小，使用二分查找可以找得到其中的区间，但因你这个值可能在多个区间内，所以要做些自己的改动。

2013年5月29日 16:28

huaye2007
60
1 1 6

添加评论

0 0

如果这些区间不是经常变化的话，可以按照中值排序，用二分搜索算法找出最接近的若干个区间，然后一一比较找出目标区间。

2013年5月28日 21:36

OpenMind
704
0 1 13

添加评论

0 0

public class Reign {

	
	Map<Integer,LinkedList<A>> reign = new HashMap<Integer, LinkedList<A>>();
	
	class A{
		public A(int min,int max){
			this.max=max;
			this.min=min;
			this.len=max-min;
		}
		int max;
		int min;
		int len;
		@Override
		public String toString() {
			return "A [max=" + max + ", min=" + min + ", len=" + len + "]";
		}
	}
	
	public void init(List<A> aList){
		for(A a:aList){
			for(int i=a.min;i<=a.max;i++){
				Integer index = Integer.valueOf(i);
				LinkedList<A> ll = reign.get(index);
				if(ll==null){
					ll= new LinkedList<A>();
					ll.add(a);
				}else{
					//遍历list，保证list按照len从小到达排序
					for(int j=0;j<ll.size();j++){
						A aa = ll.get(j);
						if(a.len<=aa.len){
							ll.add(j, a);
							break;
						}else if(j==ll.size()-1){
							ll.addLast(a);
						}
					}
				}
				reign.put(index, ll);
			}
		}
	}
	
	public static void main(String[] args) {
		Reign r = new Reign();
		List<A> a = new ArrayList<A>();
		a.add(r.new A(1, 100));
		a.add(r.new A(20, 30));
		a.add(r.new A(11, 30));
		a.add(r.new A(50, 150));
		a.add(r.new A(1, 1000));
		a.add(r.new A(200, 500));
		a.add(r.new A(300, 350));
		a.add(r.new A(500, 1000));
		a.add(r.new A(900, 1000));
		r.init(a);
		
		System.out.println(r.reign.get(Integer.valueOf(100)).get(0));
	}
	
	
}

2013年5月28日 18:01

kidding87
1566
1 1 19

2条评论

0 0

顺路告诉你个最快的方法...
数组左面是下标位.右面是所属的范围名称..没一个下标位肯定在最小范围是唯一所以
0 A0
1 A0
....
10 A1
11 A1
....
3000

然后来了数字直接返回结果了...

2013年5月28日 16:36

ansjsun
129
0 1 5

2条评论

0 0

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

public class RunTest implements Comparable<RunTest> {
	/**
	 * 区间下限
	 */
	private int floor;
	
	/**
	 * 区间上限
	 */
	private int ceil;
	
	/**
	 * 区间跨度
	 */
	private int span;

	public int getFloor() {
		return floor;
	}

	public void setFloor(int floor) {
		this.floor = floor;
	}

	public int getCeil() {
		return ceil;
	}

	public void setCeil(int ceil) {
		this.ceil = ceil;
	}

	public int getSpan() {
		return span;
	}

	public void setSpan(int span) {
		this.span = span;
	}

	public int compareTo(RunTest o) {
		if(this.span>o.getSpan()){
			return 1;
		}
		else if(this.span<o.getSpan()){
			return -1;
		}
		else{
		return 0;
		}
	}
	public String toString(){
		return "["+this.getFloor()+","+this.getCeil()+"]";
	}
	public static void main(String[] args) {
		List<RunTest> regions= new ArrayList<RunTest>();
		
		RunTest A0= new RunTest();
		A0.setFloor(1);
		A0.setCeil(3000);
		A0.setSpan(A0.getCeil()-A0.getFloor());
		
		RunTest A1= new RunTest();
		A1.setFloor(10);
		A1.setCeil(20);
		A1.setSpan(A1.getCeil()-A1.getFloor());
		
		RunTest A2= new RunTest();
		A2.setFloor(30);
		A2.setCeil(100);
		A2.setSpan(A2.getCeil()-A2.getFloor());
		regions.add(A0);
		regions.add(A1);
		regions.add(A2);
		
		int test=70;
		List<RunTest> result= new ArrayList<RunTest>();
		for(RunTest region:regions){
			if(region.getFloor()<=test&&region.getCeil()>=test){
				result.add(region);
			}
		}
		Collections.sort(result);
		System.out.println(result.get(0));
	}
}

转化为面向对象编程

2013年5月28日 13:55