Sử dụng bản đồ java cho phạm vi tìm kiếm

Question

Tôi có một trường hợp sử dụng mà nếu một số nằm giữa 0-10 nó sẽ trả về 0 và nếu nó nằm giữa 11-20 nó sẽ trả về 1 vv

0 => 0-3, (0 and 3 are inclusive) 
1 => 4-15, (4 and 15 are inclusive) 
2 => 16-40, (16 and 40 are inclusive) 
3 => 41-88, (41 and 88 are inclusive) 
5 => 89-300 (89 and 300 are inclusive) 

Tôi đã suy nghĩ làm thế nào tôi có thể thực hiện và đã suy nghĩ bản đồ java, nhưng nó không cho phép phạm vi tìm kiếm

tôi quan tâm đến một cái gì đó như thế này, tôi có một chức năng

int foo() { 

} 

nếu foo trả 5, vì nó nằm giữa 0 t o 10 Tôi sẽ sử dụng 0, nếu foo trở lại 25 nó sẽ sử dụng 2.

Bất kỳ ý tưởng

Chỉnh sửa: Thực ra các dãy là không đơn giản như 0-10, 11-20. Tôi muốn có thể thực hiện tìm kiếm theo phạm vi. Xin lỗi về sự nhầm lẫn. Dựa trên các truy vấn tôi đã thêm ví dụ chính xác, các số này liên tục

Answer 1

Tôi có thể nghĩ ra một số giải pháp khả thi cho vấn đề chung chung hơn khi phạm vi không thống nhất và có 'lỗ'. Đơn giản nhất là:

1. Chỉ cần điền Bản đồ cho tất cả các giá trị khóa hợp lệ, với nhiều ánh xạ khóa cùng một giá trị. Giả sử rằng bạn sử dụng HashMaps, đây sẽ là thời gian hiệu quả nhất (O (1) tra cứu), mặc dù bạn có nhiều công việc hơn vào thời gian thiết lập và bạn sử dụng nhiều không gian hơn.
2. Sử dụng NavigableMap và sử dụng floorEntry(key) để thực hiện tra cứu. Điều này nên được ít thời gian hiệu quả (O (log (N) tra cứu) nhưng nhiều không gian hiệu quả.

Dưới đây là một giải pháp sử dụng NavigableMaps cho phép 'lỗ' trong bản đồ.

private static class Range { 
    public int upper, value; 
    ... 
} 

NavigableMap<Integer, Range> map = new TreeMap<Integer, Range>(); 
map.put(0, new Range(3, 0));  // 0..3  => 0 
map.put(5, new Range(10, 1));  // 5..10 => 1 
map.put(100, new Range(200, 2)); // 100..200 => 2 

// To do a lookup for some value in 'key' 
Map.Entry<Integer,Range> entry = map.floorEntry(key); 
if (entry == null) { 
    // too small 
} else if (key <= entry.getValue().upper) { 
    return entry.getValue().value; 
} else { 
    // too large or in a hole 
} 

Trên Mặt khác, nếu không có 'lỗ' là giải pháp đơn giản hơn:

NavigableMap<Integer, Integer> map = new TreeMap<Integer, Integer>(); 
map.put(0, 0); // 0..4  => 0 
map.put(5, 1); // 5..10 => 1 
map.put(11, 2); // 11..200 => 2 

// To do a lookup for some value in 'key' 
if (key < 0 || key > 200) { 
    // out of range 
} else { 
    return map.floorEntry(key).getValue(); 
} 

Answer 2

Tôi nghĩ điều bạn muốn là thứ gì đó dọc theo các dòng foo()/10, nhưng điều đó sẽ cho bạn phạm vi hơi xa so với những gì bạn yêu cầu. Bạn luôn có thể thực hiện so sánh với hai điểm cuối cho mỗi mục trong "bản đồ" của bạn nếu chúng không theo một mẫu dễ dàng.

Answer 3

Trong trường hợp tổng quát hơn không thể giải quyết bằng số học, bạn có thể tạo TreeMap với một Trình so sánh phù hợp. Thêm ánh xạ cho các giá trị biên, và sau đó sử dụng ceilingEntry hoặc floorEntry để tìm kết quả phù hợp.

Answer 4

Pseudo-code:

1. Lưu giữ giới hạn phạm vi trong một mảng phẳng: new int[] {0, 3, 5, 15, 100, 300}.
2. Tìm kiếm nhị phân thông qua mảng như thể chèn một số vào mảng. Xem Arrays.binarySearch().
3. Nếu điểm chèn là chẵn, số không phù hợp với bất kỳ phạm vi nào.
4. Nếu điểm chèn là lẻ, nó phù hợp với phạm vi tương ứng. Ví dụ: điểm chèn cho 10 trong mảng trên sẽ là 3, đặt nó giữa 5 và 15, vì vậy nó nằm trong phạm vi thứ hai.

Answer 5

Tôi nghĩ giải pháp đơn giản nhất là thêm ánh xạ từ ranh giới trên của phạm vi của bạn vào giá trị của bản đồ, và tiếp tục tăng số của bạn (chính trong bản đồ) cho đến khi bạn đạt được ánh xạ (là ranh giới trên cho phạm vi số của bạn đang ở).

Một cách khác là điền bản đồ với tất cả các mục nhập trong một phạm vi và thêm ánh xạ cho từng mục.

Cách nào hiệu quả hơn tùy thuộc vào việc bạn có cần yêu cầu tất cả các số trong một phạm vi nhiều lần (sử dụng giải pháp sau) hay chỉ một vài con số một lần (sử dụng trước)