У меня есть ArrayList со следующими строками:
List<String> e = new ArrayList<String>();
e.add("123");
e.add("122");
e.add("125");
e.add("123");
Я хочу проверить список дубликатов и удалить их из списка. В этом случае мой список будет иметь только два значения, и в этом примере это будут значения 122 и 125, а два 123 будут уходить.
Каким будет лучший способ? Я думал об использовании Set, но это удалит только один из дубликатов.
В Java 8 вы можете:
e.removeIf(s -> Collections.frequency(e, s) > 1);
Если! Java 8, вы можете создать HashMap<String, Integer>. Если строка уже отображается на карте, добавьте ее ключ на один, иначе добавьте ее на карту.
Например:
put("123", 1);
Теперь предположим, что у вас есть "123", вы должны получить кол-во ключа и добавить его к нему:
put("123", get("aaa") + 1);
Теперь вы можете легко выполнить итерацию на карте и создать новый список массивов с ключами, чтобы их значения были < 2.
Литература:
Вы также можете использовать filter в Java 8
e.stream().filter(s -> Collections.frequency(e, s) == 1).collect(Collectors.toList())
Вы можете использовать HashMap<String, Integer>.
Вы перебираете список и если карта Hash не содержит строку, вы добавляете ее вместе со значением 1.
Если, с другой стороны, у вас уже есть строка, вы просто увеличиваете счетчик. Таким образом, карта для вашей строки будет выглядеть так:
{"123", 2}
{"122", 1}
{"125", 1}
Затем вы создадите новый список, где значение для каждого ключа равно 1.
Вот решение, отличное от Java 8, с использованием карты для подсчета вхождений:
Map map = new HashMap<String, Integer>()
for (String s : list){
if (map.get(s)==null){
map.put(s, 1);
}
else {
map.put(s, map.get(s)+1);
}
}
List<String> newList = new ArrayList<String>();
// Remove from list if there are multiples of them.
for (Map.Entry<String, String> entry : map.entrySet())
{
if(entry.getValue() > 1){
newList.add(entry.getKey());
}
}
list.removeAll(newList);
Решение в ArrayList
public static void main(String args[]) throws Exception {
List<String> e = new ArrayList<String>();
List<String> duplicate = new ArrayList<String>();
e.add("123");
e.add("122");
e.add("125");
e.add("123");
for(String str : e){
if(e.indexOf(str) != e.lastIndexOf(str)){
duplicate.add(str);
}
}
for(String str : duplicate){
e.remove(str);
}
for(String str : e){
System.out.println(str);
}
}
List<String> e = new ArrayList<String>();
e.add("123");
e.add("122");
e.add("125");
e.add("123");
e.add("125");
e.add("124");
List<String> sortedList = new ArrayList<String>();
for (String current : e){
if(!sortedList.contains(current)){
sortedList.add(current);
}
else{
sortedList.remove(current);
}
}
e.clear();
e.addAll(sortedList);
Простейшие решения, использующие потоки, имеют временную сложность O(n^2). Если вы попробуете их на List с миллионами записей, вы будете ждать очень и очень долгое время. Решением O(n) является:
list = list.stream()
.collect(Collectors.groupingBy(Function.identity(), LinkedHashMap::new, Collectors.counting()))
.entrySet()
.stream()
.filter(e -> e.getValue() == 1)
.map(Map.Entry::getKey)
.collect(Collectors.toList());
Здесь я использовал LinkedHashMap для поддержания порядка. Обратите внимание, что статический импорт может упростить часть collect.
Это настолько сложно, что я думаю, что использование for циклов - лучший вариант для этой проблемы.
Map<String, Integer> map = new LinkedHashMap<>();
for (String s : list)
map.merge(s, 1, Integer::sum);
list = new ArrayList<>();
for (Map.Entry<String, Integer> e : map.entrySet())
if (e.getValue() == 1)
list.add(e.getKey());
Что-то вроде этого (используя Set):
Set<Object> blackList = new Set<>()
public void add(Object object) {
if (blackList.exists(object)) {
return;
}
boolean notExists = set.add(object);
if (!notExists) {
set.remove(object)
blackList.add(object);
}
}
Если вы собираетесь установить, вы можете достичь этого с помощью двух наборов. Сохранять повторяющиеся значения в другом наборе следующим образом:
List<String> duplicateList = new ArrayList<String>();
duplicateList.add("123");
duplicateList.add("122");
duplicateList.add("125");
duplicateList.add("123");
duplicateList.add("127");
duplicateList.add("127");
System.out.println(duplicateList);
Set<String> nonDuplicateList = new TreeSet<String>();
Set<String> duplicateValues = new TreeSet<String>();
if(nonDuplicateList.size()<duplicateList.size()){
for(String s: duplicateList){
if(!nonDuplicateList.add(s)){
duplicateValues.add(s);
}
}
duplicateList.removeAll(duplicateValues);
System.out.println(duplicateList);
System.out.println(duplicateValues);
}
Выход: Исходный список: [123, 122, 125, 123, 127, 127]. После удаления
duplicate: [122, 125] значения, которые являются дубликатами: [123, 127]
Примечание. Это решение может быть не оптимизировано. Вы можете найти лучший
чем это.
Я поклонник API Google Guava. Используя утилиту Collections2 и общую реализацию Predicate, можно создать метод утилиты для покрытия нескольких типов данных.
Это предполагает, что объекты, о которых идет речь, имеют значащие .equals реализация
@Test
public void testTrimDupList() {
Collection<String> dups = Lists.newArrayList("123", "122", "125", "123");
dups = removeAll("123", dups);
Assert.assertFalse(dups.contains("123"));
Collection<Integer> dups2 = Lists.newArrayList(123, 122, 125,123);
dups2 = removeAll(123, dups2);
Assert.assertFalse(dups2.contains(123));
}
private <T> Collection<T> removeAll(final T element, Collection<T> collection) {
return Collections2.filter(collection, new Predicate<T>(){
@Override
public boolean apply(T arg0) {
return !element.equals(arg0);
}});
}
Думая об этом немного больше
Большинство других примеров на этой странице используют API java.util.List в качестве базовой коллекции. Я не уверен, что это сделано с намерением, но если возвращаемый элемент должен быть списком, может использоваться другой метод-посредник, как указано ниже. Полиморфизм ftw!
@Test
public void testTrimDupListAsCollection() {
Collection<String> dups = Lists.newArrayList("123", "122", "125", "123");
//List used here only to get access to the .contains method for validating behavior.
dups = Lists.newArrayList(removeAll("123", dups));
Assert.assertFalse(dups.contains("123"));
Collection<Integer> dups2 = Lists.newArrayList(123, 122, 125,123);
//List used here only to get access to the .contains method for validating behavior.
dups2 = Lists.newArrayList(removeAll(123, dups2));
Assert.assertFalse(dups2.contains(123));
}
@Test
public void testTrimDupListAsList() {
List<String> dups = Lists.newArrayList("123", "122", "125", "123");
dups = removeAll("123", dups);
Assert.assertFalse(dups.contains("123"));
List<Integer> dups2 = Lists.newArrayList(123, 122, 125,123);
dups2 = removeAll(123, dups2);
Assert.assertFalse(dups2.contains(123));
}
private <T> List<T> removeAll(final T element, List<T> collection) {
return Lists.newArrayList(removeAll(element, (Collection<T>) collection));
}
private <T> Collection<T> removeAll(final T element, Collection<T> collection) {
return Collections2.filter(collection, new Predicate<T>(){
@Override
public boolean apply(T arg0) {
return !element.equals(arg0);
}});
}
В библиотеке Guava, используя мультимножество и потоки:
e = HashMultiset.create(e).entrySet().stream()
.filter(me -> me.getCount() > 1)
.map(me -> me.getElement())
.collect(toList());
Это довольно и достаточно быстро для больших списков (O (n) с довольно большим постоянным множителем). Но он не сохраняет порядок (LinkedHashMultiset можно использовать, если это необходимо) и создает новый экземпляр списка.
Также легко обобщить, вместо этого, например, удалить все три раза.
В общем, структура множества мультимножеств действительно полезна для хранения в одной панели инструментов.