CODEWITHSUNDEEP
javacollectionstime-complexity
aretai
aretai

Reputation: 1641

Collections addAll method for a set of unique values

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);

Upvotes: 0

Views: 2271

Answers (2)

Vlad
Vlad

Reputation: 18633

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.

Upvotes: 0

Peter Lawrey
Peter Lawrey

Reputation: 533530

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.

Upvotes: 4

Related Questions