《力扣算法训练提升》数组篇-打卡数组统计-【41】缺失的第一个正数
《力扣算法训练提升》数组篇-打卡数组统计-【41】缺失的第一个正数
数组的基本特性
数组是最简单的数据结构。
数组是用来存储一系列相同类型数据，数据连续存储，一次性分配内存。
数组中间进行插入和删除，每次必须搬移后面的所有数据以保持连续，时间复杂度 O(N)。
数组索引
数组通过索引支持快速访问数据，一个长度为N的数组，它的下标从0开始到N-1结束。
数组元素可以通过数组名称加索引进行访问。元素的索引是放在方括号内，跟在数组名称的后边。
数组扩容
数组内存空间是一次性分配，扩容时，申请一块更大的内存空间，再将数据拷贝到新内存空间，时间复杂度为O(N)。
数组遍历
for (int i = 0; i < arr.length; i++) {
// 利用arr[i]进行数组元素操作
}
数组统计
如何统计数组中元素出现次数？
如果给定的数组元素全都是非负数，那么针对数组中元素出现个数的统计，我们可以借用额外的辅助数组来达到统计目的。
for (int i = 0; i < nums.length; i++) {
help[nums[i]]++;
}
如何快速给定元素在数组中出现的位置？左边xx位置？右边xx位置？
针对元素出现在数组左边第xx位置，右边第xx位置，依然是借助辅助数组。
借用left[]，right[] ，分别记录数组从左边开始数，第几个位置，右边数第几个位置；
for (int i = 0; i < nums.length; i++) {
left[nums[i]] = i;
}
for (int i = nums.length - 1; i >= 0 ; i--) {
right[nums[i]] = nums.length - 1 - i;
}
如何判断数组元素是否重复或者缺失？
如果数组是1~n的正数，那么可以通过修改原数组状态来进行判断；
第一次访问元素，将元素反转为负数；
第二次访问元素，判断元素状态为负数，那么此元素为重复元素；
全部状态修改完后，遍历数组，当判断元素为正数时，那么这个位置 i 就是缺失元素！
力扣【41.缺失的第一个正数】
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
具体描述
解题讨论
缺失数
归纳
缺失数一定出现在 [1, N+1] 范围内
取得数组长度为 N
第一次遍历，将所有非正数修改为 N+1
第二次遍历，打标记，将元素属于 1 ~ N 范围内的数反转为负数
第三次遍历，元素大于0，则缺失数为 下标 + 1
复杂度分析
时间复杂度：O(n)。遍历 nums 需要时间 O(n)。
空间复杂度：O(1)。不计算返回结果集，所用空间是原空间。
动画模拟
示例
public static int firstMissingPositive(int[] nums) {
// 缺失数一定出现在 [1, N+1] 范围内
// 取得数组长度为 N
// 第一次遍历，将所有非正数修改为 N+1
int N = nums.length;
for (int i = 0; i < nums.length; i++) {
if (nums[i] <= 0) {
nums[i] = N + 1;
}
}
// 第二次遍历，打标记，将元素属于 1 ~ N 范围内的数反转为负数
for (int n : nums) {
if (Math.abs(n) <= N) {
nums[Math.abs(n) - 1] = - Math.abs(nums[Math.abs(n) - 1]) ;
}
}
// 第三次遍历，元素大于0，则缺失数为 下标 + 1
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) {
return i + 1;
}
}
return N + 1;
}
短话长说
学算法，不知道从哪开始？先学什么？什么阶段该刷什么题？
按照力扣题目类别结构化排序刷题，从低阶到高阶，图解算法(更新中…)，有兴趣的童鞋，欢迎一起从小白开始零基础刷力扣，共同进步！
回复：678，获取已分类好的部分刷题顺序，后续内容会持续更新，感兴趣的小伙伴自由拿取！
另外，有关分类，求小伙伴们不要再问我最后一类的起名了，奇技淫巧是个褒义词，意思是指新奇的技艺和作品。
力扣修炼体系题目，题目分类及推荐刷题顺序及题解
目前暂定划分为四个阶段：
算法低阶入门篇--武者锻体
算法中级进阶篇--武皇炼心
算法高阶强化篇--武帝粹魂
算法奇技淫巧篇--战斗秘典
以上分类原谅我有个修仙梦...
缺漏内容，正在努力整理中…
