Использование карты Java для поиска по дальности

Question

У меня есть случай, когда число лежит в диапазоне от 0 до 10, оно должно возвращать 0, а если оно находится в диапазоне от 11 до 20, оно должно возвращать 1 и т. Д.

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)

Я думал о том, как реализовать, и думал о Java-картах, но он не позволяет искать по дальности

Меня интересует что-то подобное, у меня есть функция

int foo() {

}

если foo возвращает 5, так как он лежит в диапазоне от 0 до 10, я бы использовал 0, если foo вернул 25, он использовал бы 2.

Любые идеи

Редактировать: На самом деле диапазоны не так просты, как 0-10, 11-20. Я хочу быть в состоянии сделать поиск диапазона. Извините за путаницу. Исходя из запросов, которые я добавил правильный пример, цифры являются непрерывными

Answer 1

Я могу придумать ряд возможных решений для более общей проблемы, когда диапазоны не являются однородными и имеются «дыры». Самыми простыми являются:

1. Просто заполните Map для всех допустимых значений ключа, с несколькими ключами, отображающими одно и то же значение. Предполагая, что вы используете HashMaps, это должно быть наиболее эффективным по времени (O (1) поисков), хотя у вас больше работы во время установки и вы используете больше места.
2. Используйте NavigableMap и используйте floorEntry(key) для поиска. Это должно быть менее эффективным по времени (O (log (N)), но более эффективным.

Вот решение с использованием NavigableMaps, которое допускает «дыры» в отображении.

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
}

С другой стороны, если нет «дырок», решение проще:

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

Псевдо-код:

1. Сохранить границы диапазона в плоском массиве: new int[] {0, 3, 5, 15, 100, 300}.
2. Двоичный поиск по массиву, как если бы он вставлял число в массив. См. Arrays.binarySearch().
3. Если точка вставки четная, число не попадает ни в один диапазон.
4. Если точка вставки нечетная, она попадает в соответствующий диапазон. Например, точка вставки для 10 в приведенном выше массиве будет 3, помещая ее между 5 и 15, поэтому она принадлежит второму диапазону.

Answer 3

В более общем случае, который не может быть решен с помощью арифметики, вы можете создать TreeMap с соответствующим Comparator. Добавьте сопоставления для граничных значений, а затем используйте потолок Entry или floorEntry, чтобы найти соответствующее совпадение.

Answer 4

Я думаю, что самым простым решением было бы добавить сопоставления из верхних границ ваших диапазонов к значению, на которое отображается диапазон, и просто продолжать увеличивать свой номер (ключ на карте), пока вы не достигнете отображения (которое является верхним граница диапазона, в котором находится ваш номер).

Другим способом было бы заполнить карту всеми записями в диапазоне и добавить сопоставление для каждого.

Какой из них более эффективен, зависит от того, возможно ли, что вам нужно будет повторно запрашивать все числа в диапазоне (используйте последнее решение), или только несколько номеров (используйте первое)

Answer 5

Я думаю, что вы хотите что-то вроде foo()/10, но это даст вам немного отклонения от того, что вы просили. Вы всегда можете просто сделать сравнение с двумя конечными точками для каждого элемента на вашей «карте», если они не следуют простому шаблону.