How to count distinct Strings in ArrayList without using Set?

Question

How do you count the number of distinct Strings in an ArrayList without using the Set data structure in the Java libraries?

I made two ArrayLists, one stored and one empty and want to store the empty one with distinct Strings. What am I doing wrongly?

public void distinctCount (WordStream words) {
ArrayList<String> loaded = new ArrayList<String>();
  ArrayList<String> empty = new ArrayList<String>();
  int count = 0;

  // Fill loaded with word stream
  for(String i : words) {
    loaded.add(i);
  }

  // Fill empty with loaded
  // Catch collisions
  for(int i = 0; i < loaded.size(); i++) {
    if(loaded.get(i) != empty.get(i)) {
      empty.add(loaded.get(i));
    }
  }
  return empty.size();
}

Why the "no Set" restriction? You could add all elements to a Set then provide a List view of it. Also, "program to an interface"; prefer List<String> empty = new ArrayList<String>();. — jub0bs
– jub0bs, Commented Mar 14, 2016 at 9:00
I think you will have to scan the ArrayList for a duplicate before each addition. — Tim Biegeleisen
– Tim Biegeleisen, Commented Mar 14, 2016 at 9:02
@Jubobs Probably because it's a homework or an interview question. — Maroun
– Maroun, Commented Mar 14, 2016 at 9:05
instead of loaded.get(i) != empty.get(i) use !empty.contains(loaded.get(i)) — F. Lumnitz
– F. Lumnitz, Commented Mar 14, 2016 at 9:07

devops · Accepted Answer · 2016-03-14 09:25:05Z

3

Here is a very bad / slow option you have:

for(String s: loaded){
    if(!empty.contains(s)){
        empty.add(s);
    }
}

or if you are Java 8 fan:

empty = loaded.stream().distinct().collect(Collectors.toList())

edited Mar 14, 2016 at 9:25

answered Mar 14, 2016 at 9:06

devops

9,2016 gold badges51 silver badges77 bronze badges

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

Comments

Maroun · Accepted Answer · 2016-03-14 09:02:11Z

1

The problem is that you're comparing only corresponding elements. Meaning that you compare the n^th element with the n^th element in the second arraylist.

The straightforward solution would be having nested loops: for each element in the first arraylist, loop over all elements in the second array list, if no match found - you know it's distinct. This solution's complexity is O(n²).

Of course there are many helpful methods in the ArrayList API that can make your life much easier. If there's no restriction on other data structures, you can consider using Map as well.

answered Mar 14, 2016 at 9:02

Maroun

96.3k30 gold badges195 silver badges249 bronze badges

Comments

Danyal Sandeelo · Accepted Answer · 2016-03-14 09:03:07Z

0

use map<String,Integer>

If string exists, get the value and increment it, if there is no value against that key add 1 against that key.

answered Mar 14, 2016 at 9:03

Danyal Sandeelo

12.4k10 gold badges57 silver badges90 bronze badges

Comments

Bhadresh · Accepted Answer · 2016-03-14 09:10:36Z

Using Collections.sort() If all your list items implements Comparable, you can sort the list beforehand and then count successive items which are non equals.

private static int getUniqueCountUsingSort(List<String> list) {
    if (list.size() < 2) { // obvious case.
        return list.size();
    }

    List<String> listCopy = new ArrayList<>(list);
    Collections.sort(listCopy);
    int uniqueCount = 1;
    for (int i = 1; i < listCopy.size(); i++) { // starts at 1.
                    // Compare with previous item in the sorted list.
        if (!listCopy.get(i).equals(listCopy.get(i-1))) {
            uniqueCount ++;
        }
    }
    return uniqueCount;
}

This method has the same performance characteristics as the Set method because Collections.sort() is O(n log(n)).

By hand You can also simply do it the hard way, but it is slower O(n^2):

private static int getUniqueCountByHand(List<String> list) {

    int uniqueCount = 0;
    for (int i = 0; i < list.size(); i++) {
        boolean isUnique = true;
        // look if there is another entity before that is equal to this one.
        for (int j = 0; j < i; j++) {
            if (list.get(j).equals(list.get(i))) {
                isUnique = false;
            }
        }
        if (isUnique) {
            uniqueCount ++;
        }
    }

    return uniqueCount;
}

Devavrata · Accepted Answer · 2016-03-14 09:13:50Z

0

Use Map if you don't want to use Set.

Map<String, Integer> map=new HashMap<>();
int count=0;
for(String str:words) {
   if(map.containsKey)
      continue;
   count++;
   map.put(str,0);
}
return count;

Count will give you number of distinct strings in Arraylist word.

answered Mar 14, 2016 at 9:13

Devavrata

1,80518 silver badges30 bronze badges

Comments

matt · Accepted Answer · 2016-03-14 09:38:15Z

0

loaded.stream().filter(w->!empty.contains(w)).forEach(w->empty.add(w));

As per suggestion in the comments.

List<String> empty = loaded.stream().distinct().collect(Collectors.toList());

edited Mar 14, 2016 at 9:38

answered Mar 14, 2016 at 9:13

matt

12.4k3 gold badges28 silver badges43 bronze badges

2 Comments

marstran Over a year ago

Why not just loaded.stream().distinct().count()?

matt Over a year ago

@marstran that is much better. I added it with a collect.

Collectives™ on Stack Overflow

How to count distinct Strings in ArrayList without using Set?

6 Answers 6

Comments

Comments

Comments

Comments

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

Comments

Comments

Comments

Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related