def findMissingPositive(A):
A.sort()
return min([x for x in range(A[0], A[-1]+1) if x not in A])
a) takes O(n*lgn) time; the method in post uses O(n) time
b) use extra memory; the method in post uses O(1) extra memory
c) have logical error: the problem asks to find the first missing positive (in range [1, infinity)).
For example:
a) your firstMissingPositive([100]) gives ValueError: min() arg is an empty sequence
b) your firstMissingPositive([]) gives IndexError: list index out of range
def firstMissingPositive(A):
try:
for x in range(1, max(A)+1):
if x not in A: return x
except: return A
def firstMissingPositive(A):
try: return next(x for x in range(1, max(A)+1) if x not in A)
except: return A
print(firstMissingPositive([4,2,5,7,1])) # 3
print(firstMissingPositive([4,100])) # 1
print(firstMissingPositive([])) # []
print(firstMissingPositive([5])) # 1
Thanks for the reply, very informative.
EAFP: Easier to ask for forgiveness than permission
That being said, just a blanket except is a bad idea.
Also, I suggest first converting A to a set. Just "A = set(A)" would work.