Удалить дубликаты из отсортированного ArrayList, сохраняя при этом некоторые элементы из дубликатов

Question

Хорошо, сначала я подумал, что это будет довольно просто. Но я не могу придумать эффективный способ решить эту проблему. Я нашел способ грубой силы решить эту проблему, но это не очень элегантно. У меня есть ArrayList. Контакты - это класс VO, который имеет несколько членов - имя, регионы, идентификатор. В ArrayList есть дубликаты, потому что разные регионы появляются несколько раз. Список отсортирован по идентификатору. Вот пример:

Запись 0 - Имя: Джон Смит; Регион: N; ID: 1
Запись 1 - Имя: Джон Смит; Регион: МВт; ID: 1
Запись 2 - Имя: Джон Смит; Регион: S; ID: 1
Запись 3 - Имя: Джейн Доу; Регион: NULL; ID: 2
Запись 4 - Имя: Джек Блэк; Регион: N; ID: 3
Вступление 6 - Имя: Джек Блэк; Регион: МВт; ID: 3
Запись 7 - Имя: Джо Дон; Регион: NE; ID: 4

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

Таким образом, вывод должен выглядеть следующим образом: -

Запись 0 - Имя: Джон Смит; Регион: N, MW, S; ID: 1
Запись 1 - Имя: Джейн Доу; Регион: NULL; ID: 2
Запись 2 - Имя: Джек Блэк; Регион: N, МВт; ID: 3
Запись 3 - Имя: Джо Дон; Регион: NE; ID: 4

Что вы думаете об оптимальном способе решения этой проблемы? Я не ищу реальный код, но идеи или советы, чтобы найти лучший способ сделать это.

Спасибо за ваше время !!!

Answer 1

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

В примере кода я предполагаю, что у вас есть класс Entry с полями id, name и region, последним из которых является список экземпляров Region. Это может быть легко изменено на Set, а Region на Strings или на то, что вы используете. Образец копирует записи перед их вставкой в ​​карту, поскольку они будут изменены при объединении с другими записями.

SortedMap<Integer, Entry> mergedEntriesMap = new TreeMap<Integer, Entry>();
for (Entry e : entries) {
  if (mergedEntriesMap.contains(e.id)) {
    Entry m = mergedEntriesMap.get(e);
    m.regions.addAll(e.regions);
  } else {
    Entry m = new Entry();
    // copy the entry to keep the original array clean
    m.id = e.id;
    m.name = e.name;
    m.regions = new ArrayList<Region>(e.regions);
    mergedEntriesMap.put(m.id, m);
  }
}

List<Entry> mergedEntries = new ArrayList<Entry>(mergedEntriesMap.values());

Answer 2

Исходные данные застряли в этом формате? Если нет, вы можете захотеть изменить запрос, который вы используете для извлечения данных, сгруппировав все идентификаторы и сформировав столбец списка, разделенный запятыми. Вот пример в sql

SELECT      Id, [Name], Regions = replace
            ((SELECT Region AS [data()]
            FROM RegionTable
            WHERE  Id = u.Id
            ORDER BY Region FOR xml path('')), ' ', ', ')
FROM        [User] u
WHERE       Id IS NOT NULL
GROUP BY Id, [Name]

Answer 3

Это псевдокод, чтобы выполнить то, что вы хотите. На абстрактном уровне у вас есть список Pair<K,V> (first, second), отсортированный по K, и никакие две пары действительно не равны (то есть вы можете иметь (k1,v1) и (k1,v2), но вы не можете иметь два (k1,v1) в списке.

Вы хотите объединить последовательные пары (k,v1),(k,v2),(k,v3) в одну группу (k,[v1,v2,v3]).

List<Pair<K,V>> in;
List<Pair<K,List<V>>> out = [ ];

Pair<K,V> lastP = SENTINEL_PAIR; // lastP.first matches nothing
Pair<K,List<V>> lastGroup;

for (Pair<K,V> p : in) {
  if (p.first == lastP.first) {  // same group as last
    lastGroup.second.add(p.second);
  } else {                       // start a new group
    lastGroup = (p.first, [ p.second ]);
    out.add(lastGroup);
  }
  lastP = p;
}

В вашем случае K - это идентификатор, а V - это регион. Это O(N).

Answer 4

Вы смотрели на Google's Multimap? Он в значительной степени создан для такого типа структуры данных, в которой есть ключ, который отображается на Collection элементов. Таким образом, в этом случае String имя будет сопоставлено с Collection из Region объектов.

Multimap<String, Region> names = HashMultimap.create();
for (Entry entry : entries) {
    names.put(entry.getName(), entry.getRegion());
}
// Now u can get the collection of regions by name
Collection<Region> johnsRegions = names.get("John Smith");