6
\$\begingroup\$

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();
}
\$\endgroup\$
10
\$\begingroup\$

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();
 }
\$\endgroup\$
  • \$\begingroup\$ Thanks. I have mostly be programming in C# for the last year. That's why I have upper case on the method name \$\endgroup\$ – Harrison Brock Feb 17 '15 at 23:55
11
\$\begingroup\$

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();
}
\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
-1
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ It is still not an answer that fits Code Review. You don't review the code you're just saying hey look there is an alternative. But why are you suggesting this ? Is is faster, more readable, why would OP want to use this instead of his code ? \$\endgroup\$ – Marc-Andre Feb 18 '15 at 19:07
  • \$\begingroup\$ @Marc-Andre - thanks, I've edited the answer to reflect this. \$\endgroup\$ – Pete Becker Feb 18 '15 at 20:46
  • \$\begingroup\$ @PeteBecker thanks. You know you could use an Set<int> and use an for loop and insert into the set and get ~(N). \$\endgroup\$ – Harrison Brock Feb 19 '15 at 1:10
  • \$\begingroup\$ @hbrock - using std::set<int> would be the same as the original code, and my point was that there are other possible approaches. Note, also, that inserting N elements into a std::set is O(NlogN), not O(N). And using a hashed container will usually end up O(N) for N insertions, but that's not guaranteed; worst case is O(N^2). \$\endgroup\$ – Pete Becker Feb 19 '15 at 14:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.