def findDisappearedNumbers(self, nums): """ :type nums: List[int] :rtype: List[int] """ return list(i for i in xrange(1, len(nums)+1) if i not in nums)
@Yuukir this is not O(n) solution, it's O(n^2) because it checks whether an element in nums array.
@dmgcodevil I think we can easily convert this to O(n) in time by changing "i not in nums" to "i not in set(nums)", but this way it violates the space requirement, since set(nums) can be extra O(n) in space
changing "i not in nums" to "i not in set(nums)"
Nah, that'll make it slower.
@StefanPochmann this is interesting, I'm expecting existence test for set(nums) to be O(1). As you suggested, if it is going to be slower, I think it is either "i not in nums" is highly optimized or "set(nums)" is called every time in the for loop, which takes O(n) anyway. If latter is true, I think we can do "tmp = set(nums)" and then "i not in tmp". Can you please elaborate?
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.