Получить несколько элементов в ArrayList, которые ближе всего к целому числу

Question

У меня есть список ArrayList, состоящий из объектов. В этих объектах у меня есть поле под названием «уровень».

У меня тоже уровень игрока. Я пытаюсь получить элементы в ArrayList, ближайшем к уровню игроков, но только если уровень игроков больше, чем «уровень» в объекте.

Например:

        static {
        foodSources = new ArrayList<FoodSource>();
        foodSources.add(new FoodSource("foodSource1", 10));
        foodSources.add(new FoodSource("foodSource2", 10));
        foodSources.add(new FoodSource("foodSource3", 10));
        foodSources.add(new FoodSource("foodSource4", 12));
        foodSources.add(new FoodSource("foodSource5", 15));
        foodSources.add(new FoodSource("foodSource6", 15));
        foodSources.add(new FoodSource("foodSource7", 15));
        foodSources.add(new FoodSource("foodSource8", 20));
        foodSources.add(new FoodSource("foodSource9", 25));
    }

Если уровень игроков равен 10, он получит foodSource1, foodSource2 и foodSource3.

Если уровень игроков равен 11, он получит foodSource1, foodSource2 и foodSource3.

Однако, если уровень игрока - 12, он получит только foodSource 4.

Я пытаюсь найти эффективный способ сделать это. Я рассматривал двоичный поиск в ArrayList, но, насколько я знаю, с его помощью вы можете получить только один элемент.

Я только начал программировать снова примерно через полтора месяца go, так что я не уверен, какие функции в Java я мог бы здесь использовать.

Спасибо.

Answer 1

Вы можете создать Map<Integer, List<FoodSource>> levelToFoodSourceMap, где вы сохраняете взаимосвязь между уровнем и доступными источниками еды для этого уровня. Кроме того, вы можете написать метод, который при заданном уровне возвращает вам ближайший к уровню игрока более низкий уровень, например,

int closestLowerLevel = findClosestLevel(12);
List<FoodSource> foodSources = levelToFoodSourceMap.get(closestLowerLevel);

Доступ к карте осуществляется в постоянное время и findClosestLevel может быть реализовано в O(log(n)).

Answer 2

Правильная структура данных для этого - TreeMap, которое представляет собой двоичное дерево.

Этот ответ предоставляет информацию, которую вы ищете.

Если вы не используете TreeMap, вам придется довольствоваться поиском O (n).

int toSearch = 11;
int min = Integer.MAX_VALUE;
List<FoodSource> found = new ArrayList<>();
for (FoodSource source : foodSources) { 
    int dist = Math.abs(toSearch - source.level);
    if (dist < min) {
        min = dist;
        found.clear();
        found.add(source);
    } else if (dist == min) {
        found.add(source)
    }
}

(Это также приведет к получению foodSource4, поскольку он находится на равном расстоянии, и вы не уверены, какое поведение вы хотите в этом сценарии)

Answer 3

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

void append(TreeMap<Integer, List<FoodSource>> map, int level, FoodSource source) {
    map.putIfAbsent(level, new ArrayList<>());
    map.get(level).add(source);
}

TreeMap<Integer, List<FoodSource>> map = new TreeMap<>();
append(map, 10, new FoodSource("foodSource1", 10));
append(map, 10, new FoodSource("foodSource1", 10));
append(map, 12, new FoodSource("foodSource1", 12));
append(map, 15, new FoodSource("foodSource1", 15));

List<FoodSource> sources = map.floorKey(12).getValue();

Однако у Guava есть TreeMultimap это сделает это за вас. Единственная проблема заключается в том, что он сохраняет значения в наборе, а не в списке, поэтому элементы не упорядочиваются на заданном уровне.

TreeMultimap<Integer, FoodSource> map = TreeMultimap.create();
map.put(10, new FoodSource("foodSource1", 10));
map.put(10, new FoodSource("foodSource1", 10));
map.put(12, new FoodSource("foodSource1", 12));
map.put(15, new FoodSource("foodSource1", 15));

Set<FoodSource> sources = map.get(map.keySet().floor(12));

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

Answer 4

removeIf

Вы можете использовать эту функцию, которую я написал, которая основана на методе , упомянутом выше. Алгоритм сначала удаляет объекты со слишком высоким уровнем, а затем объекты со слишком низким уровнем, в конце у вас будет новый ArrayList с нужными объектами.

---

Код

public static ArrayList<FoodSource> find(ArrayList<FoodSource> foodSources, int level) {
    ArrayList<FoodSource> fr = new ArrayList<>(foodSources);
    // Removes objects with too high level
    fr.removeIf(n -> n.getLevel() > level);
    int max = 0;
    for (FoodSource foodSource : fr) {
        if (foodSource.getLevel() > max)
            max = foodSource.getLevel();
    }
    int finalMax = max;
    // Removes objects with too low level
    fr.removeIf(n -> n.getLevel() < finalMax);
    return fr;
}

Обратите внимание, как я создал новый список ArrayList, чтобы не изменять исходный.