IT编程 > 开发语言 > .net

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

76人参与2020-07-07

【题目】

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

 

【题目解析】

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

您对本文有任何疑问!!点此进行留言回复

推荐阅读

猜你喜欢

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

07-07

LeetCode1498. 满足条件的子序列数目

07-07

使用队列在进程中的通信

07-07

Leetcode231. 2的幂

07-07

PointNet++分类train.py

07-07

cs224n笔记05-探索词向量

07-07

拓展阅读

大家都在看

API调用微信getWXACodeUnlimit()获取小程序码

10-25

RabbitMQ单机集群搭建出现Error: unable to perform an operation on node 'rabbit1@ClusterNode1'

07-18

DotNetty在window和linux下的性能对比

03-28

.net core 图片合并,图片水印,等比例缩小,SixLabors.ImageSharp

08-09

WPF简单的分页控件实现

03-30

ASP.NET中实现中文简/繁体自动转换的类

07-02

前后端分离,https站点无法通过Ajax访问http资源(Mixed Content,The page at 'https://xxx.com' was loaded over HTTPS)

12-20

layui,返回的数据不符合规范,正确的成功状态码 (code) 应为:0

01-28

热门评论