Recursion - Removing Duplicates

Question

I'm working on a method which removes duplicates of an element in an ArrayList, recursively. But I'm running into a bit of a problem, my method works and removes some elements, but not all of the duplicates.

Here's my the input:

100, 200, 200, 300, 400, 300, 100, 500, 500, 400, 100, 400, 100, 100

And here's the output:

100, 200, 300, 400, 100, 500, 100

And my method:

public static void removeDuplicates(ArrayList<Integer> list, int counter){
    if(list == null){
        throw new NullPointerException();
    }

    if(counter < list.size()){
        if(list.contains(list.get(counter))){
            list.remove(list.lastIndexOf(list.get(counter)));
        }
        removeDuplicates(list, ++counter);
    }
}

I understand that I'm only removing the last element of said value, and then iterating to the next one. I was wondering how I should change this to remove all elements that are duplicates. Also, one part of my output that confuses me is, there are three values of '400', yet only one shows up in the output.

Thanks for the help.

It is worth noting that recursion is completely unnecessary here, and doesn't really buy you anything. Furthermore, your algorithm is very inefficient. Is there a reason you're doing things this way? — NPE
– NPE, Commented Mar 16, 2013 at 17:26
If you remove a element from ArrayList, the size of the list will be one smaller. — longhua
– longhua, Commented Mar 16, 2013 at 17:28
It's for an assignment, we have to do this with recursion. I understand that a HashSet would work wonders, and that my code is completely inefficient but we're not worried about that. — Matthew Brzezinski
– Matthew Brzezinski, Commented Mar 16, 2013 at 17:36

Matthias · Accepted Answer · 2013-03-16 17:32:31Z

2

Beside that @NPE is right (I assume this is homework), you should consider to call your function as long with the very same head, as long there is a duplicated element found. Use the next element (i.e., increase counter) only, if no duplicate is found (anymore).

answered Mar 16, 2013 at 17:32

Matthias

8,2402 gold badges30 silver badges56 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Sachin · Accepted Answer · 2013-03-16 17:35:10Z

1

Try this one:

    public static void removeDuplicates(ArrayList<Integer> list, int counter){


        if(list == null){
            throw new NullPointerException();
        }

        if(counter < list.size()){
            if(list.contains(list.get(counter))){
                if(list.lastIndexOf(list.get(counter))!=counter)
                {
                    list.remove(list.lastIndexOf(list.get(counter)));
                    counter--;
                }
            }
            removeDuplicates(list, ++counter);
        }

    }

answered Mar 16, 2013 at 17:35

Sachin

3,5944 gold badges25 silver badges45 bronze badges

Comments

wholerabbit · Accepted Answer · 2013-03-16 17:28:51Z

1

list.remove() will reduce list.size(), meaning everytime you remove an item and advance counter, you'll end up skipping one.

answered Mar 16, 2013 at 17:28

wholerabbit

11.6k2 gold badges40 silver badges73 bronze badges

Comments

Evgeniy Dorofeev · Accepted Answer · 2013-03-16 17:45:42Z

0

try

    if (counter < list.size()) {
        int i = list.lastIndexOf(list.get(counter));
        if (i > counter) {
            list.remove(i);
        } else {
            counter++;
        }
        removeDuplicates(list, counter);
    }

answered Mar 16, 2013 at 17:45

Evgeniy Dorofeev

137k31 gold badges209 silver badges288 bronze badges

Comments

Magnilex · Accepted Answer · 2013-03-16 18:08:52Z

0

My first question is why are you using recursion? Much simpler to simply build a new list from the old one.

If you work through the sequence of calls, deleting the items from your string, you will find that the output is as expected.

Pass 1 removes the last 100

100, 200, 200, 300, 400, 300, 100, 500, 500, 400, 100, 400, 100

Pass 2 removes the last 200

100, 200, 300, 400, 300, 100, 500, 500, 400, 100, 400, 100

Pass 3 removes the last 300

100, 200, 300, 400, 100, 500, 500, 400, 100, 400, 100

Pass 4 removes the last 400

100, 200, 300, 400, 100, 500, 500, 400, 100, 100

Pass 5 removes the last 100

100, 200, 300, 400, 100, 500, 500, 400, 100

Pass 6 removes the last 500

100, 200, 300, 400, 100, 500, 400, 100

Pass 7 removes nothing Pass 8 removes nothing

edited Mar 16, 2013 at 18:08

Magnilex

12k9 gold badges67 silver badges88 bronze badges

answered Mar 16, 2013 at 17:33

pnswdv

1812 silver badges8 bronze badges

Collectives™ on Stack Overflow

Recursion - Removing Duplicates

5 Answers 5

Comments

Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related