Rectangle 27 0

Removing pairs of elements in an Arraylist in Java?


public void removePairedElements(ArrayList<Integer> a){

    Collections.sort(a); //Sort a

    int i = 0;
    while(i < a.size() - 1){
      //Check if i and i+1 are the same element. If so, remove both
      if(a.get(i).equals(a.get(i+1))){
        //Remove i twice - effectively removes i and i+1
        a.remove(i);
        a.remove(i);

        //Move i *back* one index, which is equivalent to 
        //moving forward one because we just removed two elements.
        //Prevent i from becoming negative though.
        i = Math.max(0, (i - 1));
      }
      else{
        i++;
      }
    }
}

Ah, of course, because everything gets shifted over. This works flawlessly (as far as I've tested it) and looks to be the simplest code to me. Thank you so much for the help, I greatly appreciate it!

Hmmm, this concept seems to be like a good idea. It's not producing the correct output, but I think I may try to modify it and see if I can figure out whats wrong.

I got the bug, see edit - removing i+1 after removing i is effectively removing i+2, which isn't what we want.

If you're allowed to sort the arraylist, this becomes pretty simple.

O(n log n) time and O(1) space. Probably the cleanest answer. If you aren't allowed to change the ordering of the arraylist you'd have to do something else, but otherwise this should work.

Note