当前位置: 萬仟网 > IT编程>开发语言>.net > 【Leet-Code】41. 缺失的第一个正数

【Leet-Code】41. 缺失的第一个正数

2020年07月07日 .net 我要评论
【题目】给你一个未排序的整数数组,请你找出其中没有出现的最小的正整数。【题目解析】飞机对号入座,原地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是.

【题目】

给你一个未排序的整数数组,请你找出其中没有出现的最小的正整数。

 

【题目解析】

飞机对号入座,原地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

(0)
打赏 微信扫一扫 微信扫一扫

相关文章:

版权声明:本文内容由互联网用户贡献,该文观点仅代表作者本人。本站仅提供信息存储服务,不拥有所有权,不承担相关法律责任。 如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 2386932994@qq.com 举报,一经查实将立刻删除。

发表评论

验证码:
Copyright © 2017-2021  萬仟网 保留所有权利. 粤ICP备17035492号-1
站长QQ:2386932994 | 联系邮箱:2386932994@qq.com