Simple Problem but tough for me if i want it in linear time
steve at REMOVE-THIS-cybersource.com.au
Sun Aug 15 16:47:12 CEST 2010
On Sun, 15 Aug 2010 05:47:04 -0700, ChrisChia wrote:
> dataList = [a, b, c, ...]
> where a, b, c are objects of a Class X. In Class X, it contains
> self.name and self.number
> If i wish to test whether a number (let's say 100) appears in one of the
> object, and return that object,
> is that only fast way of solving this problem without iterating through
> every object to see the number value?
> dataList.__contains__ can only check my object instance name...
> anyone can solve this in linear complexity?
If all you want is *linear* time, then simply iterating over the items
will do the job:
for item in dataList:
if item.number == 100:
If you want *less* than linear time, then keep the list sorted and do a
binary search, which gives you O(log N) time. Don't sort the list each
time, because that's O(N*log N). Or use a dict, which gives you O(1) time.
More information about the Python-list