Collections addAll method for a set of unique values

Question

I am trying to find number of unique characters in a String. Solution have to be as efficient (time complexity O(N); very big arrays; in general Big O) as possible. I have decided to do it this way (if you have any better solution please let me know). The only problem is that when I try to run it it always says there is only one distinct value. It seems there is a problem with the Collections.addAll method (maybe am using it wrong). Please let me know how to fix it. It seems it is only taking first character in an array. Thank you.

    String ds = "acvdgefav";
    char[] sa = ds.toCharArray();   

    for (int i=0; i<sa.length; i++)
        System.out.println(sa[i]);
    System.out.println();
    System.out.println(sa.length);
    System.out.println();

    HashSet hs = new HashSet();
    Collections.addAll(hs, sa);
    for (int i=0; i<hs.size(); i++)
        System.out.println(sa[i]);
    System.out.println();
    int z = hs.size();
    System.out.println(z);

score 4 · Accepted Answer · answered Mar 31 '12 at 14:39

4

I suggest you use generics as it would pick up a bug in your code, as would using a debugger to step through your code.

The most efficient approach would be to use a BitSet. This is likely to be 10x faster than using a HashSet, but would have the same time complexity.

answered Mar 31 '12 at 14:39

Peter Lawrey

525,659
79
751
1,130

Please be more specific how to use BitSet with this code. I tried generics however addAll methods rejected when I tried to put HashSet into it. – aretai Mar 31 '12 at 14:48
1

`for(int i = 0; i < str.length(); i++) { bitSet.set(str.charAt(i)); } return bitSet.cardinality();` – Louis Wasserman Mar 31 '12 at 16:43

score 0 · Answer 2 · edited May 23 '17 at 11:49

0

I think using Collections.addAll like that will simply add the array itself to the set, not its characters. See also this.

import java.util.*;
class a{
    static <T> void f(T...a){
        System.out.println(a.getClass().getCanonicalName());
        System.out.println(a.length);
        System.out.println(a[0].getClass().getCanonicalName());
        System.out.println();
    }
    public static void main(String[]args){
        f(1,2,3);   
        f(new int[]{1,2,3});
        f(new Integer[]{1,2,3});
    }
}

Output:

java.lang.Integer[]
3
java.lang.Integer

int[][]
1
int[]

java.lang.Integer[]
3
java.lang.Integer

Basically a variable arguments method taking a generic array will end up with an Object..., implemented as an Object[], which isn't compatible with int[], so the int[] gets boxed.

Also, this:

for (int i=0; i<hs.size(); i++)
     System.out.println(sa[i]);

is wrong. There is no relationship between i and characters in sa.

edited May 23 '17 at 11:49

Community

1
1

answered Mar 31 '12 at 14:38

Vlad

18,195
4
41
71

Well what I tried to do was to use the set specification (no duplicate elements) and simply add all elements from the array into a set (duplicates wouldn't be added) so in short only distinct values would be there. Then use size() and I got it. You are right about the line (copy-paste eh) Iterator i = hs.iterator(); while(i.hasNext()) System.out.println(i.next()); but then it returns some irrelevant value. I checked both Collections.addAll() and Arrays.asList() only thought this way would be more efficient – aretai Mar 31 '12 at 14:52
I was wrong about `Arrays.asList`, I think the same thing happens. – Vlad Mar 31 '12 at 16:33
then I will need to downgrade you;) – aretai Mar 31 '12 at 17:07

Collections addAll method for a set of unique values

2 Answers2