Сортировка по карте на основе порядка числового ключа

У меня есть Map<String,Map<Integer,String>>Сортировка по карте на основе порядка числового ключа

Sample данные А на этой карте

("aa" , ((3, "xx"),(5, "yy"),(1,"zz"))) 

("bb" , (5, "zz"))

Здесь Integer ключ внутренней карты лежит между 1 до 5. Это в основном a номер приоритета.

Теперь мне нужно получить значение для некоторого ключа (скажем aa). Он должен возвращать значения из внутренней карты с наивысшим номером приоритета (ключ).

В приведенном выше примере необходимо вернуть yy.

Примечание: порядок ввода данных на карту не имеет никакого отношения к порядку ключа внутренней карты.

Что я должен делать -

Используйте отсортирован внутреннюю карту на основе ключа при заполнении данных карты?
Итерировать по карте с наивысшим приоритетом (5 в данном случае) до самого низкого (1 в данном случае)?
Отсортировать внутреннюю карту в порядке возрастания ключа и получить последнее значение?

источник

2016-09-20 dev ツ

Не будет ли второе 'aa' переопределять первое значение? Я предполагаю, что это должно быть «Map >>' –

@DeendayalGarg Я думаю, что вторая 'aa' просто ссылалась на добавление другого значения во внутреннюю карту. – 4castle

@DeendayalGarg i обновленный вопрос –

Варианты 2 & 3 менее эффективны, потому что вам придется сортировать/повторять каждый раз, когда вы проводите опрос на значение.

Вы можете реализовать опцию №1 с помощью TreeMap, и все сортировки будут обработаны для вас по мере добавления элементов. Затем используйте TreeMap#lastEntry(), чтобы получить запись с наивысшим значением ключа.

Используя некоторые функции Java 8:

Map<String,TreeMap<Integer,String>> outerMap = new HashMap<>(); 

public void insert(String outerKey, Integer innerKey, String innerValue) { 
    outerMap.computeIfAbsent(outerKey, k -> new TreeMap<>()) 
     .put(innerKey, innerValue); 
} 

public String pollHighest(String outerKey) { 
    return Optional.of(outerKey) 
     .map(outerMap::get) 
     .map(TreeMap::lastEntry) 
     .map(Map.Entry::getValue) 
     .orElse(null); 
}

источник

2016-09-20 17:17:53 4castle

спасибо за образец кода, используя Java8 Но я использую Java 7. Хотя я получил вашу мысль. –

Если никакие другие операции не выполняются на этой карте, им лучше идти с опцией # 1, который строит карту в соответствии с требованием. Нет необходимости в дальнейших итерациях.

Предлагаю использовать treeMap для innerMap на основе ключа.

источник

2016-09-20 17:18:54

Пожалуйста, проверьте обновленный вопрос. –

Добавляет ли это больше, чем мой ответ? Если вы согласны с существующим ответом, просто переверните. – 4castle

Вариант № 2 будет иметь O(n) сложность в худшем случае.

Вариант № 3 будет нуждаться в сортировке на каждом шагу. Это будет O(n) в худшем случае, если вы вставляете элементы один за другим, используя алгоритм сортировки вставки.

Для внутренней карты вы можете использовать TreeMap. Он сохранит данные, отсортированные для вас. TreeMap гарантии log(n) сложность времени для операций. Для вашего случая также может использоваться очередь приоритетов (сделанная с использованием максимальной кучи).

источник

2016-09-20 18:00:29

Одна вещь, которую следует учитывать при использовании очереди приоритетов, заключается в том, что она позволит дублировать. – 4castle

Да, приоритетная очередь позволяет дублировать. Но, я не думаю, что это повлияет на требование выше. Локальные значения могут быть устранены логикой. –

Сортировка по карте на основе порядка числового ключа

ответ

Смежные вопросы