Random commentary about Machine Learning, BigData, Spark, Deep Learning, C++, STL, Boost, Perl, Python, Algorithms, Problem Solving and Web Search
Thursday, March 17, 2011
Find single element
You are given an array A that contains integers. Every integer occurs 3 times in A leaving one integer that appears only once. Fastest way to find that single integer
Need to look through entire array (of a length N) to be sure, and one approach could be to use 2 hash tables while doing that, one for occurence (or count) of all element numbers and one for occurence of single elements - this can be done in O(N)
Need to look through entire array (of a length N) to be sure, and one approach could be to use 2 hash tables while doing that, one for occurence (or count) of all element numbers and one for occurence of single elements - this can be done in O(N)
ReplyDeletecode:
https://gist.github.com/878167
The vector contains n+1 unique and 2*n reps, so I can stop when the size of first hash reaches n+1 items.
ReplyDelete