Remove non-unique numbers from arraylist with O(1) space

Question

I am trying to remove all numbers that are not unique from an arraylist. I have to do this without adding more than O(1) space. Here is my code:

static ArrayList<Integer> removeDup(ArrayList<Integer> arrayOfNumbers) {
 Collections.sort(arrayOfNumbers);

    ArrayList<Integer> singleVals = new ArrayList<Integer>();
    boolean found = false;
    for (int i = 0; i < arrayOfNumbers.size(); i++) {
        int temp = arrayOfNumbers.get(i);
        for(int j = i+1; j < arrayOfNumbers.size(); j++)
        {
            if(temp == arrayOfNumbers.get(j))
            {
                arrayOfNumbers.remove(arrayOfNumbers.get(j));
                while(j != arrayOfNumbers.size()-1 && temp == arrayOfNumbers.get(j))
                {
                    arrayOfNumbers.remove(arrayOfNumbers.get(j));
                }
                if(temp == arrayOfNumbers.get(j))
            {
                arrayOfNumbers.remove(arrayOfNumbers.get(j));
            }
                found = true;
            }
        }
        if(found == true)
        {
            arrayOfNumbers.remove(arrayOfNumbers.get(i));
            found = false;
        }
    }
    System.out.println( Arrays.toString(arrayOfNumbers.toArray()));
    return arrayOfNumbers;
}


public static void main(String[] args) {
 ArrayList<Integer>values = new ArrayList<Integer>();
        values.add(1);
        values.add(2);
        values.add(3);
        values.add(4);
        values.add(4);
        values.add(5);
        values.add(6);
        values.add(7);
        values.add(7);
        values.add(8);
        values.add(9);
        values.add(10);
        values.add(11);
        values.add(11);
        values.add(11);
        values.add(11);
        values.add(11);
        values.add(12);
        values.add(12);
        values.add(13);
        values.add(13);
        values.add(13);
        values.add(13);

           removeDup(values);
}

My code is removing all of the duplicates except the two 12's. I'm not sure what I am missing with this edge case. Please help.

Removing from a list while iterating it produces unpredictable behavior. It would be better to use an iterator instead. — Vasan, Oct 31 '17 at 14:05
@Vasan I've never done this before, are you able to show me code? — Demetrius, Oct 31 '17 at 14:08
https://docs.oracle.com/javase/7/docs/api/java/util/Iterator.html#remove() and https://stackoverflow.com/questions/10431981/remove-elements-from-collection-while-iterating (or any of the matches for "iterator remove java") — Vasan, Oct 31 '17 at 14:11
How do I put the iterator values into the original arraylist? — Demetrius, Oct 31 '17 at 14:29
@Jack Any removals you make to the iterator are visible in the list directly, because it is backed by the list. — Vasan, Oct 31 '17 at 14:33

DAle · Answer 1 · 2017-10-31T14:37:45.383

1

For removing duplicates in-place in the sorted array you can just move unique elements to the left part of the array and then remove the remaining part:

static ArrayList<Integer> removeDup(ArrayList<Integer> a) {
    Collections.sort(a);    

    int uniqueCnt = 0; 
    for (int i = 0; i < a.size(); ++i) {
        if ((i == 0 || a.get(i) != a.get(i-1)) && (i+1 == a.size() || a.get(i) != a.get(i+1))) {
            a.set(uniqueCnt++, a.get(i));
        }
    } 
    a.subList(uniqueCnt, a.size()).clear();
    return a;
}

Runnable version: https://ideone.com/HoHmYE

edited Oct 31 '17 at 14:37

answered Oct 31 '17 at 14:13

DAle

8,990
2
26
45

This code is removing the duplicates of the numbers but isn't deleting all instances of the numbers that have repeats. I want just the original numbers that had no repeats. This just removes the repeats. – Demetrius Oct 31 '17 at 14:33
@Jack, sorry, misread the question. Now it removes duplicates. – DAle Oct 31 '17 at 14:38

achAmháin · Answer 2 · 2017-10-31T14:03:11.977

0

You can remove all duplicates in a list in one line:

List<Integer> removed = list.stream().distinct().collect(Collectors.toList());

Try it online

edited Oct 31 '17 at 14:03

answered Oct 31 '17 at 14:02

achAmháin

4,176
4
17
40

OP mentions O(1) space, not time. – Vasan Oct 31 '17 at 14:02
@Vasan oh so he does, my bad. – achAmháin Oct 31 '17 at 14:03
@Vasan O(1) time is not possible for a problem like this – Sujal Mandal Oct 31 '17 at 18:08

Remove non-unique numbers from arraylist with O(1) space

2 Answers2