Increase efficiency of finding and using duplicate elements in an ArrayList-CodePudding

My task is to take an ArrayList<SomeType>, and check for duplicate elements. If there is a duplicate element found && it has the same someClassProperty as the first element, use the duplicate element as a parameter in a function call. In the end, remove the duplicates from the original List and the function returns the number of duplicates. (Sorry if my explanation is poor, please look at my code then it's easy to understand)

The problem here is that the code I've come up with is very inefficient and slow, I can't figure out how to make it faster.

public int removeDuplicateElements(){
    List<SomeType> duplicates = new ArrayList<SomeType>();
    for (int i = 0; i < ListWithDuplicates.size(); i  ) {
        SomeType firstElement = ListWithDuplicates.get(i);
        for (int j = i   1; j < ListWithDuplicates.size(); j  ) {
            SomeType otherElement = ListWithDuplicates.get(j);
            assert firstElement != otherElement;
            if (firstElement.sameProperty(otherElement.getProperty())) {
                duplicates.add(otherElement);
                firstElement.someFunction(otherElement);
            }
        }
    }
    for (SomeType duplicate : duplicates) {
        ListWithDuplicates.remove(duplicate);
    }
    return duplicates.size();
}

CodePudding user response：

Assuming your property implements hashCode() and equals(), you can use it as a key in a HashMap to efficiently exclude duplicates and construct a new list from the remaining values:

public int removeDuplicateElements() {
    Map<Property, SomeType> uniques = new HashMap<>();
    for (SomeType element : ListWithDuplicates) {
        uniques.putIfAbsent(element.getProperty(), element);
    }
    int duplicates = ListWithDuplicates.size() - uniques.size();
    ListWithDuplicates = new ArrayList<>(uniques.values());
    return duplicates;
}

A more streamy variant on the above map:

Map<Property, SomeProperty> uniques = ListWithDuplicates.stream()
        .collect(Collectors.toMap(SomeType::getProperty, e -> e, (a, b) -> a));

CodePudding user response：

You code runs in O(n^2) time complexity, we can reduce the time complexity by two ways

Sorting the Array

 public static <T extends Comparable<T>> int removeDuplicateElements(List<T> listWithDuplicates) {
        Collections.sort(listWithDuplicates);
        for(int i = 0 ; i < listWithDuplicates.size() - 1 ; i  ) {
            if(listWithDuplicates.get(i).equals(listWithDuplicates.get(i 1))) {
                listWithDuplicates.remove(i--);
            }
        }
        return listWithDuplicates.size();
    }

By doing it this way, we reduce the Time Complexity to O(nlogn) but we lose the order of the original array.

Hash Table

public static <T extends Comparable<T>> int removeDuplicateElements(List<T> listWithDuplicates) {
        HashMap<T,Boolean> hashMap = new HashMap<>();
        for(int i = 0 ; i < listWithDuplicates.size() ; i  ) {
            if(hashMap.containsKey(listWithDuplicates.get(i)))
                listWithDuplicates.remove(i--);
            else
                hashMap.put(listWithDuplicates.get(i),true);
        }
        return listWithDuplicates.size();
    }

With this way we reduce the time complexity to O(n) but we exchanged it for O(n) memomry complexity.