CODEWITHSUNDEEP
javaalgorithmdata-structurescomplexity-theorybig-o
codeofnode
codeofnode

Reputation: 18619

Is searching possible in O(1) time?

I have a list of objects, objectList, where each object have several attributes one of these is myUniqueNo. myUniqueNo is a random integer for each object. I have an integer, say, n. I am sure that in objectList there is certainly an object that has the myUniqueNo as n. I want to return the object that have 'myUniqueNo' as n. Is there any O(1) algorithm or simply a method in Java to return this object?

Upvotes: 1

Views: 257

Answers (1)

templatetypedef
templatetypedef

Reputation: 372824

The typical approach for this would be to have an auxiliary HashMap that maps from the object to the position in the list. Hash tables give expected amortized O(1) lookups, though if you try removing items from in the middle of the list you will have to do an extra O(n) work to update the hash table entries.

Hope this helps!

Upvotes: 5

Related Questions