给定一个无重复元素的整数数组nums,请你找出其中没有出现的最小的正整数
进阶: 空间复杂度 ,时间复杂度
数据范围:
class Solution: def minNumberDisappeared(self , nums: List[int]) -> int: # 方法一: 快速查找考虑用hash表 tab_hash = {val:1 for val in nums} for i in range(1, len(nums) + 2): val = tab_hash.get(i) if val is None: return i # 方法二: 排序 def minNumberDisappeared(self , nums: List[int]) -> int: # write code here nums.sort() ind = 0 for i in range(1, len(nums) + 2): if i > nums[-1]: return i while True: if i == nums[ind]: ind += 1 break if i > nums[ind]: ind += 1 if i < nums[ind]: return i
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param nums int整型一维数组 # @return int整型 # class Solution: def minNumberDisappeared(self , nums: List[int]) -> int: # write code here n=len(nums) d=dict() for i in range(n): num=nums[i] if not d.get(num) and num>0: d[num]=1 for i in range(1,n+2):#从1到n+1中找,而不是[1,n] if not d.get(i): return i
class Solution: def minNumberDisappeared(self , nums: List[int]) -> int: # 排序 nums.sort() # 遍历列表,找到第一个大于0的元素 for i in range(len(nums)): if nums[i] <=0: continue else: id = i break # 如果该元素大于1,直接返回1 if nums[id] > 1: return 1 # 否则,继续遍历,当第i个元素与第i+1个元素不相等,且不连续时,输出nums[i]+1 for i in range(id,len(nums)-1): if nums[i]!= nums[i+1] and nums[i]+1 != nums[i+1]: return nums[i]+1 # 最坏的情况,遍历完整个数组 return nums[-1]+1
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param nums int整型一维数组 # @return int整型 # class Solution: def minNumberDisappeared(self , nums: List[int]) -> int: # write code here if len(nums) == 0: return 1 elif 1 not in nums: return 1 else: nums.sort() t = nums.index(1) tmp = nums[t:] for i in range(len(tmp)-1): if tmp[i]+1 != tmp[i+1]: return tmp[i]+1 return tmp[-1]+1
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param nums int整型一维数组 # @return int整型 # class Solution: def minNumberDisappeared(self , nums: List[int]) -> int: # write code here save = 1 nums.sort() for i in nums: if(i<=0): continue elif(i == save): save += 1 continue else: #break return save return save
class Solution: def minNumberDisappeared(self , nums: List[int]) -> int: # write code here n=len(nums) for i in range(n): if nums[i]<0: nums[i]=n+1 if min(nums)>1: return 1 v=n+min(nums) dp=[False]*v for i in nums: if i <=v: dp[i-1]=True for i in range(min(nums)-1,len(dp)): if dp[i]==False: return i+1 return n