Doombringer
Doombringer

Reputation: 674

Algorithm for removing duplicates from ArrayList

I have an ArrayList<String> that contains the following:

2#3#1#0

1#0#4#1

9#2#5#0

4#2#3#2

1#1#2#1

Output: 6 different numbers.

I'm trying to write an algorithm that removes duplicates of the highlighted numbers so I can then use a counter to see how many different numbers in total in all of those locations are.

I've tried many things including some of the following: [Java remove duplicates from array using loops][1], [Java - Removing duplicates in an ArrayList][2], the first option in [How to find duplicates in Java array?][3] and many more. I've spent at least 5-10h just trying to figure what I'm doing wrong, but I can not, so I've turned to you.

Most of the time the solutions I find online seem to work on simple stuff, but not in my case. In it, when I try to print the different characters, it always returns the wrong int numbers.

I've also tried, also tried separating each line of numbers into a different int Array[] and then comparing, but it just won't catch all the different values.

In another example where I had 5 different numbers in total, I kept getting "4 different" as a result, so I even tried long n = ArrayList.stream().distinct().count(); just to see if I was doing something wrong, but even this thing returned "4 different" numbers.

I know the easiest way is using Set and Map, but I don't want that. I'd like to have an algorithm.

EDIT:

One of the many things I've tried is the following:

for (int m = 0; m < (size-1); m++){
        for (int j = m + 1; j < size; j++){
            if (ArrayList.get(j).charAt(0) != ArrayList.get(m).charAt(0)){
                continue;
            }
            current++;
            ArrayList.remove(j).charAt(0);
            j--;
            size--;
        }
    }

With this one, I'd have to use another one for the ArrayList.get().charAt(4).

EDIT2:

I've found the following code [here][1], but how would it be implemented in this case?

public static <T> ArrayList<T> uniquefy(ArrayList<T> myList) {

    ArrayList <T> uniqueArrayList = new ArrayList<T>();
    for (int i = 0; i < myList.size(); i++){
        if (!uniqueArrayList.contains(myList.get(i))){
            uniqueArrayList.add(myList.get(i));
        }
    }

    return uniqueArrayList;
}

EDIT3: I've found a possible solution, but it gives me an IndexOutOfBoundsException. I've put the numbers 2, 1, 9, 4, 1 into Array1 and 1, 4, 5, 3, 2 into Array2, but when I try to compare them, I get the mentioned error.

boolean stopSequence = false;
    for (int i = 0; i < Array1.length; i++){
        for (int a = 0; a < Array2.length && !stopSequence;){
            if (Array1[i] != Array2[a]){
                Array1[i] = 0;
                a++;
            }
            if (Array1[i] == Array2[a]){
                Array1[i] = 0;
                stopSequence = true;
            }
        }
        stopSequence = false;
    }

[1]: https://stackoverflow.com/questions/26998156/java-remove-duplicates-from-array-using-loops
[2]: https://stackoverflow.com/questions/2435156/java-removing-duplicates-in-an-arraylist
[3]: http://javarevisited.blogspot.com.es/2015/06/3-ways-to-find-duplicate-elements-in-array-java.html
[4]: https://stackoverflo

w.com/questions/203984/how-do-i-remove-repeated-elements-from-arraylist?rq=1

Upvotes: 2

Views: 557

Answers (4)

JB Nizet
JB Nizet

Reputation: 692281

The algorithm is much simpler than what you think it is:

  1. transform every string into a pair of characters
  2. putting all the characters into a collection or stream that removes duplicates
  3. counting the number of characters.

Here is a complete example:

import java.util.Arrays;
import java.util.List;
import java.util.stream.IntStream;

public class Duplicates {
    public static void main(String[] args) {
        List<String> list = Arrays.asList("2#3#1#0",
                                          "1#0#4#1",
                                          "9#2#5#0",
                                          "4#2#3#2",
                                          "1#1#2#1");
        System.out.println(
            list.stream()
                .flatMapToInt(s -> IntStream.of(s.charAt(0), s.charAt(4)))
                .distinct()
                .count());
    }
}

EDIT: You seem to want to obey absurd restrictions, and thus neither use a Stream nor a Set, where these completely make sense. Here's code only using lists, but doing basically the same thing as above, but in a much less efficient way:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Duplicates {
    public static void main(String[] args) {
        List<String> list = Arrays.asList("2#3#1#0",
                                          "1#0#4#1",
                                          "9#2#5#0",
                                          "4#2#3#2",
                                          "1#1#2#1");
        List<Character> uniqueChars = new ArrayList<>();
        for (String s : list) {
            Character c0 = s.charAt(0);
            Character c4 = s.charAt(4);

            if (!uniqueChars.contains(c0)) {
                uniqueChars.add(c0);
            }
            if (!uniqueChars.contains(c4)) {
                uniqueChars.add(c4);
            }
        }

        System.out.println(uniqueChars.size());
    }
}

Upvotes: 3

Oghli
Oghli

Reputation: 2351

It's not that difficult to count different numbers of the highlighted locations.you can use helper array called frequency array to get the expected result.

Try this simple algorithm using frequency array I think it worked perfectly for your case:

       ArrayList<String> numlist=new ArrayList<String>();
       int freq[] = new int [10];
       numlist.add("2#3#1#0");
       numlist.add("1#0#4#1");
       numlist.add("9#2#5#0");
       numlist.add("4#2#3#2");
       numlist.add("1#1#2#1");
       for(int i = 0; i < numlist.size(); i++){
           String row = numlist.get(i);          
           int numValue1 = Character.getNumericValue(row.charAt(0));
           int numValue2 = Character.getNumericValue(row.charAt(4));
           freq[numValue1]++;
           freq[numValue2]++;          
       }
       int count = 0;
       for(int i = 0; i < 10; i++){
           if(freq[i] > 0){
               count++;
           }
       }
       System.out.println(count + " different numbers");

Output:

6 different numbers

Upvotes: 2

gil.fernandes
gil.fernandes

Reputation: 14641

Another option with bit masks:

public static void main(String[] args) {
    List<String> arrayList = Arrays.asList("2#3#1#0", "1#0#4#1", "9#2#5#0", "4#2#3#2", "1#1#2#1");
    int mask = 0;
    for(String s : arrayList) { // Place the bits
        mask = mask | (1 << Character.getNumericValue(s.charAt(0))) | (1 << Character.getNumericValue(s.charAt(4)));
    }
    int counter = 0;
    for(int i = 0; i < 32; i++) { // count the bits
        counter += (mask & (1 << i)) == 1 << i ? 1 : 0;
    }
    System.out.println(counter);
}

Output:

6

This relies on the bit mask which is at the end of the execution of the code:

1000111110

Possibly this is faster than most solutions, since it does not rely on conventional data structures.

Upvotes: 1

Little Santi
Little Santi

Reputation: 8833

Well, a good practice is always to divide the problem into smaller parts:

For example, a good design would be a class with these members:

  • digits: This is an instance variable of array of ints to contain the number of times each digit was repeated. It must be pre-sized to the maximum allowed digit (I guess that is 9).
  • differentDigits: The is an instance variable to contain the number of different digits.
  • processList: This method shall receive the list to browse it and call processItem for each item.
  • processItem: This method shall receive an item String and parse the digits according to the specified format (through StringTokenizer, for example), and call storeDigit for each required digit.
  • storeDigit: This method shall receive an int and use it to index the instance array digits, and increment the indexed position. If the indexed position was 0, it should also increment differentDigits.

Upvotes: 0

Related Questions