给定一个未排序的整数数组，找出其中未出现的最小正整数。

• Python 官网：https://www.python.org/

• Free：大咖免费“圣经”教程《 python 完全自学教程》，不仅仅是基础那么简单……
  
  地址：https://lqpybook.readthedocs.io/

  自学并不是什么神秘的东西，一个人一辈子自学的时间总是比在学校学习的时间长，没有老师的时候总是比有老师的时候多。
            —— 华罗庚

• My CSDN主页、My HOT博、My Python 学习个人备忘录
• 好文力荐、 老齐教室

本文质量分：

CSDN质量分查询入口：http://www.csdn.net/qc

• ◆缺失的第一个正数
• • 1、题目描述
  • 2、大佬题解
  • • 2.1 CV的“原码”
    • 2.2 读不明白的算法
    • 2.3 读懂代码
  • 3、我的理解
  • • 3.1 借轮“出海”
  • 4、用成员判定in解题
  • 5、完整源码

◆缺失的第一个正数

1、题目描述

  给你一个未排序的整数数组nums，请你找出其中没有出现的最小的正整数。请你实现时间复杂度为 O(n) 并且只使用常1数级别额外空间的解决方案。

样例 1：

输入：
nums = [1, 2, 0]

输出：
3

样例2:

输入：
nums = [3, 4, -1, 1]

输出：
2

样例 3：

输入：
nums = [7, 8, 9, 11, 12]

输出：
1

提示：

• 1 <= nums.length <= 5 * 10⁵
• -2³¹ <= nums[i] <= 2^{31 - 1}
  
  

2、大佬题解

   从大佬的博文中剪来的题解代码，其中while一段以我目前水准读不明白。

2.1 CV的“原码”

class Solution:def firstMissingPositive(self, nums: List[int]) -> int:n = len(nums)for i in range(n):while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:input(nums) nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]for i in range(n):if nums[i] != i + 1:return i + 1return n + 1

以上这段代码的逻辑：
  “_{好在题目没说参数空间不可以修改，不说就是默认，我们就用参数的空间。我们把在范围内的正数放在对应的位置，处理完一遍数组后，第二次遍历数组，对应位置数字不对的就是缺失的正数。}”

def firstMissingPositive(self, nums: List[int]) -> int:pass

  这函数形参的定义语法，我的两个Python环境都“死活”不认。😣


  函数定义原语句，修改成了我Python喜欢的样子，才成功跑起来了。

def firstMissingPositive(self, nums) -> int:pass

2.2 读不明白的算法

  以我目前的Python学识，读不明白那while那一段代码，加了两个print()“显形”，才晓得是起“排序”作用。😝

代码

def firstMissingPositive(self, nums) -> int:n = len(nums)for i in range(n):print(nums) # 添加的调试用语句。while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]print(nums) # 添加的调试用语句。

效果截屏

2.3 读懂代码

  经过仔细拆解，终于读懂大佬算法代码。

  原来大佬说的“……把在范围内的正数放在对应的位置，处理完一遍数组后……”，意思是遍历一遍数组，把<=数组长度len(nums)的正整数放在其对应的正确位置_{(设定数组第一个位置放1)}，依次处理每个正整数。nums[nums[i] - 1] != nums[i]的意义是遍历到的数组元素值减1不等于它的下标，即nums[i] - 1 != i，因此可以换为后面一句的写法。

class Solution:#def firstMissingPositive(self, nums: List[int]) -> int:def firstMissingPositive(self, nums) -> int:n = len(nums)for i in range(n):print('\n遍历位置：i =', i)#while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:while 0 < nums[i] <= n and nums[i] - 1 != i:print(nums)nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]        print(f"\n{nums}\n") for i in range(n):if nums[i] != i + 1:return i + 1return n + 1

如：



  样例3给出的整数都大于其长度5，不作处理。第一个位置不是1，1即是未出现过的最小正整数。

3、我的理解

  题目要求从给定数组中找出未出现过的最小正整数，正整数即是不含“0”的自然数，那么从1开始升序查找判定就好。首先对数组升序排序_{(题目描述中没说明不可以用轮子，我认为调用或者自码排序代码，都是可行的)}，然后截取正数部分比对判定，找出未出现过最小正整数。

3.1 借轮“出海”

  借用list.sort()排正序，enumerate()枚举同时遍历下标和数组元素本身。

代码

def findmin(nums):''' 找出数列中未出现的最小正数 '''nums = [i for i in nums if i > 0] # 列表解析出给定数组的自然数部分。nums.sort() # 排正序。list.sort()默认正序。for k,i in enumerate(nums):if nums[k+1] - 1 != i:return i + 1return i + 1

4、用成员判定in解题

  用Python成员判定指令in来解题，无须对nums输入数组排序。用msx(nums)取出最大整数，遍历1～最大整数的整数列表，依次判定在不在数组num中，当i in nums的值为False时，即找到缺失的最小整数。这个算法只需遍历“最小缺失值”次 _{(从1~n依次遍历)}，我觉得是“易读易懂”的轻便算法。

代码

def findmin(nums):''' 找出数列中未出现的最小正数 '''for i in range(1, max(nums)):if i not in nums: # not False即是True。return i

5、完整源码

(源码较长，点此跳过源码)

我的HOT博：

• New：ChatGPT初体验_{(ChatGPT国内镜像站初体验，聊天、Python代码生成。)CSDN质量分}92。(30687阅读)
• 尼姆游戏_{(彩色文字界面版，\033控制码实现。Linux系统有效。)CSDN质量分}xx。(1001阅读)
• 神奇的 \033 ，让打印出彩(1739阅读)
• 小炼二维数组(1764阅读)
• 仿真模拟福彩双色球(2622阅读)
• Python之魔幻切片(1417阅读)
• 数列求和a, aa, aaa, ..., aa...aa(n个a)(1729阅读)
• 个人信息提取(2671阅读)
• 中文字符命名Python变量和函数(1021阅读)
• 我的Python学习笔记(1021阅读)
• 十六进制字符串转Python代码(utf-8字符串转十六进制字符串)(1319阅读)
• 生成100个随机正整数(2489阅读)
• 给定字符串提取姓名(字符串、list、re“零宽断言”)(1842阅读)
• 我的 Python.color() (Python 色彩打印控制)(2370阅读)
• python清屏(3150阅读)
• 回车符、换行符和回车换行符(3558阅读)
• Linux 脚本文件第一行的特殊注释符(井号和感叹号组合)的含义(2301阅读)
• random.sample()将在python 3.9x后续版本中被弃用(2045阅读)
• pandas 数据类型之 Series(1809阅读)
• 聊天消息敏感词屏蔽系统(字符串替换 str.replace(str1, *) )(2332阅读)
• 练习：银行复利计算(用 for 循环解一道初中小题)(2159阅读)
• pandas 数据类型之 DataFrame(5932阅读)
• 班里有人和我同生日难吗？(蒙特卡洛随机模拟法)(2921阅读)
• Python 续行符(\)“拯救”你的超长语句(1502阅读)
• Python字符串居中显示(4684阅读)
• 练习：求偶数和、阈值分割和求差( list 对象的两个基础小题)(2331阅读)
• 用 pandas 解一道小题(2268阅读)
• 可迭代对象和四个函数(1752阅读)
• “快乐数”判断(1847阅读)
• 罗马数字转换器(构造元素取模)(3157阅读)
• Hot：罗马数字(转换器|罗生成器)(5783阅读)
• Hot：让QQ群昵称色变的代码(49777阅读)
• Hot：斐波那契数列(递归| for )(4719阅读)
• 柱状图中最大矩形(2348阅读)
• 排序数组元素的重复起止(1964阅读)
• 电话拨号键盘字母组合(2170阅读)
• 密码强度检测器(3124阅读)
• 求列表平衡点(2498阅读)
• Hot：字符串统计(4581阅读)
• Hot：尼姆游戏(聪明版首发)(4135阅读)
• 尼姆游戏(优化版)(1968阅读)

• 
  

  推荐条件点阅破千

  ---

  回页首

  ---

  
  

  精品文章：

  • 好文力荐：齐伟书稿 《python 完全自学教程》 Free连载(已完稿并集结成书，还有PDF版本百度网盘永久分享，点击跳转免费🆓下载。)
  • OPP三大特性：封装中的property
  • 通过内置对象理解python'
  • 正则表达式
  • python中“*”的作用
  • Python 完全自学手册
  • 海象运算符
  • Python中的 `!=`与`is not`不同
  • 学习编程的正确方法

  来源：老齐教室

  ---

  回页首

  ---

  ◆ Python 入门指南【Python 3.6.3】

  ---

  好文力荐：

  • 全栈领域优质创作者——寒佬(还是国内某高校学生)博文“非技术文—关于英语和如何正确的提问”，“英语”和“会提问”是学习的两大利器。

  • 【8大编程语言的适用领域】先别着急选语言学编程，先看它们能干嘛

  • 靠谱程序员的好习惯

  ---

  CSDN实用技巧博文：

  • 8个好用到爆的Python实用技巧
  • python忽略警告
  • Python代码编写规范
  • Python的docstring规范（说明文档的规范写法）

  ---