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.