- #1
daniel_i_l
Gold Member
- 868
- 0
Let's say I have an unsorted array of integers. Is it possible to determine if there exists a number in the array that appears only once with a time complexity of less than O(nlogn)? Sorting the array takes nlogn time so I'm wondering if it's possible without sorting. I don't need to return the element, only to determine that it exists.
I think that the answer is no. If it was possible than it'd also be possible to check if two sets are equal or not in less that nlogn time since you could simply connect the sets and check if there's a unique element. Does anyone know the best algorithm for checking if two sets are equal?
Thanks,
Daniel
I think that the answer is no. If it was possible than it'd also be possible to check if two sets are equal or not in less that nlogn time since you could simply connect the sets and check if there's a unique element. Does anyone know the best algorithm for checking if two sets are equal?
Thanks,
Daniel