алгоритм — C ++ Удалить дублирование в наборе списка

Question

алгоритм — C ++ Удалить дублирование в наборе списка

Я пытаюсь удалить дубликаты в списке возврата в этот вопрос

Учитывая набор номеров кандидатов (C) и целевого числа (T), найдите все уникальные комбинации в C, где номера кандидатов суммируются с T.

Каждое число в C может использоваться только один раз в комбинации.

Замечания:

Все числа (включая цель) будут положительными целыми числами.
Элементы в комбинации (a1, a2,…, ak) должны быть в не убывающем порядке. (то есть a1 ≤ a2 ≤… ≤ ak).
Набор решений не должен содержать повторяющихся комбинаций.

Например, данный набор кандидатов 10,1,2,7,6,1,5 и цель 8,
Набор решений:

[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]

Мой вопрос, как эффективно удалить дублирование?
Вот мой код:

public class Solution {
public static void main(String[] args) {
int[] input = { 10, 1, 2, 7, 6, 1, 5 };
// int[] input = { 2, 1, 1, 4, 4, 2 };
System.out.println(combinationSum2(input, 8));
}

private static class Entry {
List<Integer> list;
int target;
int index; // the previous index

public Entry(int target) {
list = new LinkedList<Integer>();
this.target = target;
}

public int add(int num, int index) {
this.list.add(num);
this.index = index;
this.target -= num;
return target;
}

public Entry copy() {
Entry copy = new Entry(this.target);
copy.list = new ArrayList<>();
copy.list.addAll(list);
copy.target = target;
copy.index = index;
return copy;
}

}

public static List<List<Integer>> combinationSum2(int[] input, int target) {
List<List<Integer>> ret = new LinkedList<List<Integer>>();

if (null == input || input.length <= 0)
return ret;

Arrays.sort(input);

int N = input.length;
Queue<Entry> pool = new LinkedList<Entry>();
for (int i = 0; i < N; i++) {
if (input[i] <= target) {
Entry entry = new Entry(target);
entry.add(input[i], i);
pool.add(entry);
}
}

while (!pool.isEmpty()) {
Entry cur = pool.poll();
if (cur.target == 0) {
ret.add(cur.list);
} else if (cur.target > 0) {
for (int i = cur.index + 1; i < N; i++) {
if (cur.target - input[i] >= 0) {
Entry copy = cur.copy();
copy.add(input[i], i);
pool.offer(copy);
} else {
break;
}
}
}
}

return ret;
}
}

Моя первая идея — отсортировать списки в возвращаемом списке, сравнить их один за другим, чтобы удалить дубликаты. Но есть ли более быстрый способ? или любое предложение?

4

algorithm c++combinations deduplication list

Решение

Другие решения

Вы можете удалить дубликаты или повторяющиеся элементы из List в Java, преобразовав List в HashSet в Java. но прежде чем делать это, просто имейте в виду, что Set не сохраняет порядок вставки, который гарантирован List, на самом деле это основное отличие между List и Set в Java.

Поэтому, когда вы конвертируете List в HashSet, все дублирующиеся элементы будут удалены, но порядок вставки будет потерян.

Более подробное объяснение можно найти Вот

3

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

По сути, пройти список от головы до конца. Для каждого вновь обнаруженного элемента мы проверяем, находится ли он в хэш-наборе (HashSet): если да, мы удаляем его; иначе мы вставим это.

1

Источник

Accepted Answer

Я предлагаю использовать HashSet, чтобы предотвратить добавление любой существующей записи.
Первое, что нужно сделать, это переопределить функцию equals и hashCode для вашего класса Entry. (больше материала)

private static class Entry {
List<Integer> list;
int target;
int index;
int hash; // <---- add this

public Entry(int target) {
list = new LinkedList<Integer>();
this.target = target;
hash = target;
}

public int add(int num, int index) {
this.list.add(num);
this.index = index;
this.target -= num;
hash = hash * 17 + num;
return target;
}

public Entry copy() {
Entry copy = new Entry(this.target);
copy.list = new ArrayList<>();
copy.list.addAll(list);
copy.target = target;
copy.index = index;
copy.hash = hash;
return copy;
}

@Override
public boolean equals(Object obj) {
Entry e = (Entry) obj;
if ((this.target != e.target) || (this.list.size() != e.list.size())) {
return false;
}
for (int i = 0; i < this.list.size(); i++) {
if (!this.list.get(i).equals(e.list.get(i)))
return false;
}
return true;
}

@Override
public int hashCode() {
return hash;
}
}

Следующим шагом является использование хэш-набора для фильтрации результатов.

Set<Entry> nodup = new HashSet<Entry>();

while (!pool.isEmpty()) {
Entry cur = pool.poll();
if (cur.target == 0) {
nodup.add(cur);
} else if (cur.target > 0) {
// ... your code
}
}

for (Entry entry : nodup) {
ret.add(entry.list);
}

4