У меня есть список типов Integer, например:
[1, 1, 2, 3, 3, 3]
Я хотел бы, чтобы метод возвращал все дубликаты, например:
[1, 3]
Каков наилучший способ сделать это?
У меня есть список типов Integer, например:
[1, 1, 2, 3, 3, 3]
Я хотел бы, чтобы метод возвращал все дубликаты, например:
[1, 3]
Каков наилучший способ сделать это?
Метод add
из Set
возвращает логическое значение, если значение уже существует (true, если оно не существует, false, если оно уже существует, см. Документацию Set).
Так что просто переберите все значения:
public Set<Integer> findDuplicates(List<Integer> listContainingDuplicates)
{
final Set<Integer> setToReturn = new HashSet<>();
final Set<Integer> set1 = new HashSet<>();
for (Integer yourInt : listContainingDuplicates)
{
if (!set1.add(yourInt))
{
setToReturn.add(yourInt);
}
}
return setToReturn;
}
Мне тоже нужно было это решить. Я использовал решение Leifg и сделал его универсальным.
private <T> Set<T> findDuplicates(Collection<T> collection) {
Set<T> duplicates = new LinkedHashSet<>();
Set<T> uniques = new HashSet<>();
for(T t : collection) {
if(!uniques.add(t)) {
duplicates.add(t);
}
}
return duplicates;
}
Я принял решение Джона Стриклера и переделал его, чтобы использовать API потоков, введенный в JDK8:
private <T> Set<T> findDuplicates(Collection<T> collection) {
Set<T> uniques = new HashSet<>();
return collection.stream()
.filter(e -> !uniques.add(e))
.collect(Collectors.toSet());
}
int[] nums = new int[] {1, 1, 2, 3, 3, 3};
Arrays.sort(nums);
for (int i = 0; i < nums.length-1; i++) {
if (nums[i] == nums[i+1]) {
System.out.println("duplicate item "+nums[i+1]+" at Location"+(i+1) );
}
}
Очевидно, что вы можете делать с ними все, что хотите (т.е. ставить в Set, чтобы получить уникальный список повторяющихся значений), а не печатать... Это также полезно для записи местоположения повторяющихся элементов.
Вот решение с использованием Streams с Java 8
// lets assume the original list is filled with {1,1,2,3,6,3,8,7}
List<String> original = new ArrayList<>();
List<String> result = new ArrayList<>();
Вы просто смотрите, если частота этого объекта более чем один раз в вашем списке. Затем вызовите .distinct(), чтобы в вашем результате были только уникальные элементы
result = original.stream()
.filter(e -> Collections.frequency(original, e) > 1)
.distinct()
.collect(Collectors.toList());
// returns {1,3}
// returns only numbers which occur more than once
result = original.stream()
.filter(e -> Collections.frequency(original, e) == 1)
.collect(Collectors.toList());
// returns {2,6,8,7}
// returns numbers which occur only once
result = original.stream()
.distinct()
.collect(Collectors.toList());
// returns {1,2,3,6,8,7}
// returns the list without duplicates
Базовое решение Java 8:
List duplicates =
list.stream().collect(Collectors.groupingBy(Function.identity()))
.entrySet()
.stream()
.filter(e -> e.getValue().size() > 1)
.map(Map.Entry::getKey)
.collect(Collectors.toList());
Это также работает:
public static Set<Integer> findDuplicates(List<Integer> input) {
List<Integer> copy = new ArrayList<Integer>(input);
for (Integer value : new HashSet<Integer>(input)) {
copy.remove(value);
}
return new HashSet<Integer>(copy);
}
Использование Guava на Java 8
private Set<Integer> findDuplicates(List<Integer> input) {
// Linked* preserves insertion order so the returned Sets iteration order is somewhat like the original list
LinkedHashMultiset<Integer> duplicates = LinkedHashMultiset.create(input);
// Remove all entries with a count of 1
duplicates.entrySet().removeIf(entry -> entry.getCount() == 1);
return duplicates.elementSet();
}
Вы можете использовать что-то вроде этого:
List<Integer> newList = new ArrayList<Integer>();
for(int i : yourOldList)
{
yourOldList.remove(i);
if(yourOldList.contains(i) && !newList.contains(i)) newList.add(i);
}
Используйте MultiMap для хранения каждого значения в качестве набора ключей/значений. Затем выполните итерацию по клавишам и найдите те, у которых есть несколько значений.
Ламбас может быть решением
Integer[] nums = new Integer[] {1, 1, 2, 3, 3, 3};
List<Integer> list = Arrays.asList(nums);
List<Integer> dps = list.stream().distinct().filter(entry -> Collections.frequency(list, entry) > 1).collect(Collectors.toList());
Если вы используете Eclipse Collections, это будет работать:
MutableList<Integer> list = Lists.mutable.with(1, 1, 2, 3, 3, 3);
Set<Integer> dupes = list.toBag().selectByOccurrences(i -> i > 1).toSet();
Assert.assertEquals(Sets.mutable.with(1, 3), dupes);
Обновление: Начиная с Eclipse Collections 9.2, теперь вы можете использовать selectDuplicates
MutableList<Integer> list = Lists.mutable.with(1, 1, 2, 3, 3, 3);
Set<Integer> dupes = list.toBag().selectDuplicates().toSet();
Assert.assertEquals(Sets.mutable.with(1, 3), dupes);
Вы также можете использовать примитивные коллекции для достижения этой цели:
IntList list = IntLists.mutable.with(1, 1, 2, 3, 3, 3);
IntSet dupes = list.toBag().selectDuplicates().toSet();
Assert.assertEquals(IntSets.mutable.with(1, 3), dupes);
Примечание: я являюсь коммиттером для Eclipse Collections.
создать Map<Integer,Integer>
, перебрать список, если элемент находится на карте, увеличить его значение, в противном случае добавить его к карте с ключом = 1
итерации карты и добавьте в список все элементы с ключом >= 2
public static void main(String[] args) {
List<Integer> list = new LinkedList<Integer>();
list.add(1);
list.add(1);
list.add(1);
list.add(2);
list.add(3);
list.add(3);
Map<Integer,Integer> map = new HashMap<Integer, Integer>();
for (Integer x : list) {
Integer val = map.get(x);
if (val == null) {
map.put(x,1);
} else {
map.remove(x);
map.put(x,val+1);
}
}
List<Integer> result = new LinkedList<Integer>();
for (Entry<Integer, Integer> entry : map.entrySet()) {
if (entry.getValue() > 1) {
result.add(entry.getKey());
}
}
for (Integer x : result) {
System.out.println(x);
}
}
Это проблема, когда блестят функциональные методы. Например, следующее решение F # является более четким и менее подверженным ошибкам, чем лучшее императивное решение Java (и я ежедневно работаю как с Java, так и с F #).
[1;1;2;3;3;3]
|> Seq.countBy id
|> Seq.choose (fun (key,count) -> if count > 1 then Some(key) else None)
Конечно, этот вопрос касается Java. Поэтому мое предложение - принять библиотеку, которая предоставляет функциональные возможности Java. Например, его можно было бы решить, используя мою собственную библиотеку следующим образом (и есть еще несколько других, на которые стоит обратить внимание):
Seq.of(1,1,2,3,3,3)
.groupBy(new Func1<Integer,Integer>() {
public Integer call(Integer key) {
return key;
}
}).filter(new Predicate<Grouping<Integer,Integer>>() {
public Boolean call(Grouping<Integer, Integer> grouping) {
return grouping.getGrouping().count() > 1;
}
}).map(new Func1<Grouping<Integer,Integer>,Integer>() {
public Integer call(Grouping<Integer, Integer> grouping) {
return grouping.getKey();
}
});
Компактная генерализованная версия верхнего ответа, также добавленная пустая проверка и предварительно выделенный размер Set:
public static final <T> Set<T> findDuplicates(final List<T> listWhichMayHaveDuplicates) {
final Set<T> duplicates = new HashSet<>();
final int listSize = listWhichMayHaveDuplicates.size();
if (listSize > 0) {
final Set<T> tempSet = new HashSet<>(listSize);
for (final T element : listWhichMayHaveDuplicates) {
if (!tempSet.add(element)) {
duplicates.add(element);
}
}
}
return duplicates;
}
public class practicese {
public static void main(String[] args) {
List<Integer> listOf = new ArrayList<Integer>();
listOf.add(3);
listOf.add(1);
listOf.add(2);
listOf.add(3);
listOf.add(3);
listOf.add(2);
listOf.add(1);
List<Integer> tempList = new ArrayList<Integer>();
for(Integer obj:listOf){
if(!tempList.contains(obj)){
tempList.add(obj);
}
}
System.out.println(tempList);
}
}
Аналогично некоторым ответам здесь, но если вы хотите найти дубликаты на основе некоторого свойства:
public static <T, R> Set<R> findDuplicates(Collection<? extends T> collection, Function<? super T, ? extends R> mapper) {
Set<R> uniques = new HashSet<>();
return collection.stream()
.map(mapper)
.filter(e -> !uniques.add(e))
.collect(toSet());
}
Попробуйте найти дубликаты в списке:
ArrayList<String> arrayList1 = new ArrayList<String>();
arrayList1.add("A");
arrayList1.add("A");
arrayList1.add("B");
arrayList1.add("B");
arrayList1.add("B");
arrayList1.add("C");
for (int x=0; x< arrayList1.size(); x++)
{
System.out.println("arrayList1 :"+arrayList1.get(x));
}
Set s=new TreeSet();
s.addAll(arrayList1);
Iterator it=s.iterator();
while (it.hasNext())
{
System.out.println("Set :"+(String)it.next());
}
Это должно работать для сортировки и несортировки.
public void testFindDuplicates() {
List<Integer> list = new ArrayList<Integer>();
list.add(1);
list.add(1);
list.add(2);
list.add(3);
list.add(3);
list.add(3);
Set<Integer> result = new HashSet<Integer>();
int currentIndex = 0;
for (Integer i : list) {
if (!result.contains(i) && list.subList(currentIndex + 1, list.size()).contains(i)) {
result.add(i);
}
currentIndex++;
}
assertEquals(2, result.size());
assertTrue(result.contains(1));
assertTrue(result.contains(3));
}
public class DuplicatesWithOutCollection {
public static void main(String[] args) {
int[] arr = new int[] { 2, 3, 4, 6, 6, 8, 10, 10, 10, 11, 12, 12 };
boolean flag = false;
int k = 1;
while (k == 1) {
arr = removeDuplicate(arr);
flag = checkDuplicate(arr, flag);
if (flag) {
k = 1;
} else {
k = 0;
}
}
}
private static boolean checkDuplicate(int[] arr, boolean flag) {
int i = 0;
while (i < arr.length - 1) {
if (arr[i] == arr[i + 1]) {
flag = true;
} else {
flag = false;
}
i++;
}
return flag;
}
private static int[] removeDuplicate(int[] arr) {
int i = 0, j = 0;
int[] temp = new int[arr.length];
while (i < arr.length - 1) {
if (arr[i] == arr[i + 1]) {
temp[j] = arr[i + 1];
i = i + 2;
} else {
temp[j] = arr[i];
i = i + 1;
if (i == arr.length - 1) {
temp[j + 1] = arr[i + 1];
break;
}
}
j++;
}
System.out.println();
return temp;
}
}
import java.util.Scanner;
public class OnlyDuplicates {
public static void main(String[] args) {
System.out.print(" Enter a set of 10 numbers: ");
int[] numbers = new int[10];
Scanner input = new Scanner(System.in);
for (int i = 0; i < numbers.length; i++) {
numbers[i] = input.nextInt();
}
numbers = onlyDuplicates(numbers);
System.out.print(" The numbers are: ");
for (int i = 0; i < numbers.length; i++) {
System.out.print(numbers[i] + "");
}
}
public static int[] onlyDuplicates(int[] list) {
boolean flag = true;
int[] array = new int[0];
array = add2Array(array, list[0]);
for (int i = 0; i < list.length; i++) {
for (int j = 0; j < array.length; j++) {
if (list[i] == array[j]) {
flag = false;
break;
}
}
if (flag) {
array = add2Array(array, list[i]);
}
flag = true;
}
return array;
}
// Copy numbers1 to numbers2
// If the length of numbers2 is less then numbers2, return false
public static boolean copyArray(int[] source, int[] dest) {
if (source.length > dest.length) {
return false;
}
for (int i = 0; i < source.length; i++) {
dest[i] = source[i];
}
return true;
}
// Increase array size by one and add integer to the end of the array
public static int[] add2Array(int[] source, int data) {
int[] dest = new int[source.length + 1];
copyArray(source, dest);
dest[source.length] = data;
return dest;
}
}
Это был бы хороший способ найти повторяющиеся значения без использования Set.
public static <T> List<T> findDuplicates(List<T> list){
List<T> nonDistinctElements = new ArrayList<>();
for(T s : list)
if(list.indexOf(s) != list.lastIndexOf(s))
if(!nonDistinctElements.contains(s))
nonDistinctElements.add(s);
return nonDistinctElements;
}
И скажем, вам нужен метод, который возвращает вам отдельный список, т.е. если вы передадите список, в котором элементы встречаются более одного раза, вы получите список с различными элементами.
public static <T> void distinctList(List<T> list){
List<T> nonDistinctElements = new ArrayList<>();
for(T s : list)
if(list.indexOf(s) != list.lastIndexOf(s))
nonDistinctElements.add(s);
for(T nonDistinctElement : nonDistinctElements)
if(list.indexOf(nonDistinctElement) != list.lastIndexOf(nonDistinctElement))
list.remove(nonDistinctElement);
}
И версия, которая использует метод commons-collections
CollectionUtils.getCardinalityMap
:
final List<Integer> values = Arrays.asList(1, 1, 2, 3, 3, 3);
final Map<Integer, Integer> cardinalityMap = CollectionUtils.getCardinalityMap(values);
System.out.println(cardinalityMap
.entrySet()
.stream().filter(e -> e.getValue() > 1)
.map(e -> e.getKey())
.collect(Collectors.toList()));
"""
Как насчет этого кода -
public static void main(String[] args) {
//Lets say we have a elements in array
int[] a = {13,65,13,67,88,65,88,23,65,88,92};
List<Integer> ls1 = new ArrayList<>();
List<Integer> ls2 = new ArrayList<>();
Set<Integer> ls3 = new TreeSet<>();
//Adding each element of the array in the list
for(int i=0;i<a.length;i++) {
{
ls1.add(a[i]);
}
}
//Iterating each element in the arrary
for (Integer eachInt : ls1) {
//If the list2 contains the iterating element, then add that into set<> (as this would be a duplicate element)
if(ls2.contains(eachInt)) {
ls3.add(eachInt);
}
else {ls2.add(eachInt);}
}
System.out.println("Elements in array or ls1"+ls1);
System.out.println("Duplicate Elements in Set ls3"+ls3);
}
на всякий случай для тех, кто также хочет включить как дубликаты, так и не дубликаты. в основном ответ похож на правильный ответ, но вместо того, чтобы вернуться, если не часть, вы возвращаете остальную часть
используйте этот код (измените на нужный вам тип)
public Set<String> findDup(List<String> Duplicates){
Set<String> returning = new HashSet<>();
Set<String> nonreturning = new HashSet<>();
Set<String> setup = new HashSet<>();
for(String i:Duplicates){
if(!setup.add( i )){
returning.add( i );
}else{
nonreturning.add( i );
}
}
Toast.makeText( context,"hello set"+returning+nonreturning+" size"+nonreturning.size(),Toast.LENGTH_SHORT ).show();
return nonreturning;
}
Я взял ответ Себастьяна и добавил к нему ключевой экстрактор -
private <U, T> Set<T> findDuplicates(Collection<T> collection, Function<? super T,? extends U> keyExtractor) {
Map<U, T> uniques = new HashMap<>(); // maps unique keys to corresponding values
return collection.stream()
.filter(e -> uniques.put(keyExtractor.apply(e), e) != null)
.collect(Collectors.toSet());
}
Потокобезопасная альтернатива:
/**
* Returns all duplicates that are in the list as a new {@link Set} thread-safe.
* <p>
* Usually the Set will contain only the last duplicate, however the decision
* what elements are equal depends on the implementation of the {@link List}. An
* exotic implementation of {@link List} might decide two elements are "equal",
* in this case multiple duplicates might be returned.
*
* @param <X> The type of element to compare.
* @param list The list that contains the elements, never <code>null</code>.
* @return A set of all duplicates in the list. Returns only the last duplicate.
*/
public <X extends Object> Set<X> findDuplicates(List<X> list) {
Set<X> dups = new LinkedHashSet<>(list.size());
synchronized (list) {
for (X x : list) {
if (list.indexOf(x) != list.lastIndexOf(x)) {
dups.add(x);
}
}
}
return dups;
}
Более общий метод как вариант fooobar.com/questions/79390/...
/**
* Returns a duplicated values found in given collection based on fieldClassifier
*
* @param collection given collection of elements
* @param fieldClassifier field classifier which specifies element to check for duplicates(useful in complex objects).
* @param <T> Type of element in collection
* @param <K> Element which will be returned from method in fieldClassifier.
* @return returns list of values that are duplocated.
*/
public static <T, K> List<K> lookForDuplicates(List<T> collection, Function<? super T, ? extends K> fieldClassifier) {
return collection.stream().collect(Collectors.groupingBy(fieldClassifier))
.entrySet()
.stream()
.filter(e -> e.getValue().size() > 1)
.map(Map.Entry::getKey)
.collect(Collectors.toList());
}
Поместите список в набор (это эффективно фильтрует только уникальные элементы), удалите все заданные элементы из исходного списка (поэтому он будет содержать только элементы, которые имеют более 1 вхождения) и поместите список в новый набор (это снова будет фильтровать только уникальные предметы):
List<Item> list = ...;
list.removeAll(new HashSet<Item>(list));
return new HashSet<Item>(list);
Если вы знаете максимальное значение (например, 10000), вы можете пожертвовать пространством для скорости. Я не могу вспомнить точное название этой техники.
псевдокод:
//does not handle case when mem allocation fails
//probably can be extended to unknown values /larger values .
maybe by sorting first
public List<int> GetDuplicates(int max)
{
//allocate and clear memory to 0/false
bit[] buckets=new bit[max]
memcpy(buckets,0,max);
//find duplicates
List<int> result=new List<int>();
foreach(int val in List)
{
if (buckets[val])
{
result.add(value);
}
else
{
buckets[val]=1;
}
}
return result
}