给你一个未排序的整数数组,请你找出其中没有出现的最小的正整数。
飞机对号入座,原地O(N)解法!
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
for a in nums: #遍历每个座位,记当前坐着a号乘客
while 0<a<=len(nums) and a!=nums[a-1]: #乘客a是正票但坐错了! 其座位被 ta=nums[a-1]占了
nums[a-1], a = a, nums[a - 1] # a和ta两人互换则a对号入座。此后ta相当于新的a,去找自己的座位(循环执行)
#print(nums)
for i in range(len(nums)):
if i+1!=nums[i]:
return i+1 #找到首个没有对号入座的nums[i]!=i+1
return len(nums)+1 #满座,返回N+1
注意:
题解中:如果将:nums[a-1], a = a, nums[a-1] 换成 a, nums[a-1] = nums[a-1], a 是错误的!
本文地址:https://blog.csdn.net/wdh315172/article/details/107156953
如对本文有疑问, 点击进行留言回复!!
Spark系列(一)Spark简介与架构以及Spark安装流程(单机版和分布式版)---轻松上手Spark流处理
淘淘商城第60讲——搭建Solr集群时,报错:org.apache.solr.common.SolrException: Could not find collection : core1
只用time模块,检查y年中有多少个星期w,并且返回所有符合日期
网友评论