Описание
Ввод List<Item>
отсортирован по баллам, Item
выглядит следующим образом:
class Item {
double score;
String category;
String author;
String poi;
}
Теперь мне нужно выбрать 10 элементов, которые имеют самые высокие оценки из массива, с учетом этих ограничений:
- Они должны иметь разные
poi
- У них должен быть другой
author
- Есть максимум 3 пунктов из одной и той же
category
. И длина любой подпоследовательности из той жеcategory
не должна превышать 2.
Если нет подпоследовательности, которая удовлетворяет вышеуказанным правилам, просто верните первые 10 элементов.
Что я пробовал
Теперь я напрямую перебираю List
и использую три HashMap<String, Integer>
для хранения cagetory/poi/author
вида каждого cagetory/poi/author
. И я использую List<Item> selected
чтобы сохранить результат.
- Если уже есть выбранный элемент, имеющий эту
poi
, то новый элемент будет отброшен. - Если уже есть выбранный элемент, у которого есть этот
author
, то новый элемент будет отброшен. - Если уже есть три выбранных элемента, которые имеют эту
category
, то новый элемент будет отброшен. - Если в хвосте
selected
элемента уже есть два элемента, которые имеют этуcategory
, то новый элемент будет отброшен.
проблема
Он работает, когда вход большой, но когда вход относительно небольшой, он не работает. Например, когда ввод
- Item1 (Категория A, Автор 1)
- Item2 (Категория A, Автор 2)
- Item3 (Категория A, Автор 3)
- Item4 (Категория B, Автор 2)
- Item5 (Категория C, Автор 5)
- Item6 (Категория D, Автор 6)
- Item7 (Категория E, Автор 7)
- Item8 (Категория F, Автор 8)
- Item9 (Категория G, Автор 9)
- Item10 (Категория H, Автор 10)
- Item11 (категория I, автор 11)
Тогда мое решение будет
-
Item3
отбрасывается, потому что он имеет ту жеcategory
что иItem1
иItem2
-
Item4
отброшен, потому что у него есть тот жеauthor
что иItem2
- 9 других элементов остаются.
И это не удовлетворяет select top 10 elements
. Правильное решение - отказаться от Item2
и должно остаться только 10 элементов.
Вопрос
Я думаю, что мое решение просто в неправильном направлении. Поэтому я ищу другие решения для решения этой проблемы. Любое решение дает желаемый результат.