Number of distinct elements in an array

Question

This is my solution to find the Number of distinct elements in an array. Is there away fast way to do this? It run-time is O(N).

    public int DistinctNumberOfItems( int[] A ) {

        if (A.length == 0) return 0;
        if(A.length == 1) return 1;

        Set<Integer> set = new TreeSet<Integer>();

        for (int i : A) {

            set.add(i);
    }
        return set.size();
}

Answer 1

What you primarily need is a bit of code formatting, naming conventions, and best practices.

• Your formatting is messed up, use your IDE's auto formatting feature
• Method names and parameter names start with lowercase letters. Avoid one-letter variables, array is a better name.
• A TreeSet is sorted, but there is no need to keep the set sorted, use a HashSet instead
• Use array.length <= 1 for a simpler if check at the beginning.

End result:

 public int distinctNumberOfItems(int[] array) {
     if (array.length <= 1) {
         return array.length;
     }

     Set<Integer> set = new HashSet<Integer>();
     for (int i : array) {
        set.add(i);
     }
     return set.size();
 }

Answer 2

Your code was better in Rev 1. I don't know why you changed it. Whenever you can get away without special cases, it's probably better to do so.

This code is a pure function of the input array and nothing else. Therefore, it would probably be better as a static function.

Renaming the function from NumberOf… to …Count would make it less verbose. You should also respect Java naming conventions, in which method names start with a lowercase letter. The parameter name A also has unconventional capitalization.

As others have said, your algorithm, using TreeSet, is O(n log n). You would need a HashSet for O(n). When constructing a HashSet, it's a good idea to provide an estimate of the collection size, since a wrong guess would hurt performance.

public static int distinctItemCount(int[] array) {
    Set<Integer> set = new HashSet<Integer>(array.length);
    for (int i : array) {
        set.add(i);
    }
    return set.size();
}

Answer 3

Think of it this way: is there any way to count the number of distinct elements without actually looking at every element? (More accurately, without looking at some substantial portion of the elements?) If not, then \$O(N)\$ is the best you can do, asymptotically. There might be other optimizations you can make to speed things up in wall clock time, but the algorithm is as fast as it can be.

I suspect, though, that your code isn't actually running in \$O(N)\$ worst-case time, because I suspect that adding an item to a Java TreeSet is an \$O(\log N)\$ operation, since I think they're implemented with Red-Black Trees. If you process \$n\$ items, and each time you process an item you do something with it that takes \$\log n\$ time, then your algorithm has worst-case complexity \$O(n \log n)\$.

A Java hash set, which uses a hash table, should insert in \$O(1)\$ time, so your code would run in \$O(N)\$ worst-case time if you used a HashSet<Integer> (as Simon André Forsberg suggests too) instead of a TreeSet. In general, I think that's the best you can do if you're just looking at an arbitrary array of items.

Answer 4

Maybe substitute the two if statements with:

if (A.length == 1 || A.length == 0)
    return A.length;

Seems tidier to me.

But I also like how you've solved your problem because it's clear what you're doing which is also important.

Answer 5

Another approach is to just do it. I haven't programmed in Java in a long time, so here's how I'd do it in C++:

int number_of_distinct_elements(std::vector<int> data) {
    std::sort(data.begin(), data.end());
    auto last = std::unique(data.begin(), data.end());
    return last - data.begin();
}

One advantage of this approach is that it doesn't pound memory with a bunch of discrete allocations for a node-based container. Another is that it says what it does, instead of leaving it to the reader to figure out how the original code eliminates duplicates.

You may have to write your own counterpart to std::unique, but that's straightforward.

Note that this is a different algorithm than the one under review.