Hmm. I don't think they claimed to have an O(1) time solution, just O(1) added space. Which, it is, but only because they're counting on the original array's underlying type having enough bits for their sign flipping. It would be as if you used a more compact type for the array elements, and then allocated another bitmap for the range of numbers.

Of course, once we start optimizing how the original array is stored, we may have exceeded the limits of this problem as a teaching exercise :)

As for time, it does seem to be O(n) to me; can you clarify why you think it's nlogn? It may not be particularly fast in practice when compared to other O(n) approaches like the bitmap, but I don't think the complexity is wrong.

Your solution is nice - it actually gives you more information (how many appearances, not just T/F >1 appearance), but it does require more additional space and isn't necessarily faster. I think the bitmap approach would be nicer if you're ok with using more space; the bitmap is essentially a very easy to find perfect hash function due to the unique input constraints.