牛客热题:数组中出现一次的两个数字> 📟作者主页:慢热的陕西人
🌴专栏链接:力扣刷题日记
📣欢迎各位大佬👍点赞🔥关注🚓收藏,🍉留言
文章目录
- 牛客热题:缺失的第一个正整数
- 题目链接
- 方法一:排序
- 思路
- 代码
- 复杂度
- 方法二:哈希表
- 思路
- 代码
- 复杂度
- 方法三:原地哈希
- 思路
- 代码
- 复杂度
- 总结
牛客热题:缺失的第一个正整数
题目链接
缺失的第一个正整数_牛客题霸_牛客网 (nowcoder.com)
方法一:排序
思路
- step1: 先将数组进行排序
- step2:引入一个计数count = 1;
- step3:当数组大于零的时候并且当前遍历的值等于count的时候–count++
- step4: 当遍历的数组元素已经大于count了,这时候退出循环,代表已经找到了对应的缺失的整数
代码
int minNumberDisappeared(vector<int>& nums) {int count = 1;sort(nums.begin(), nums.end());for(auto num : nums){if(num > 0){if(count == num){count++;}else if(count < num){break;}}}return count;}
复杂度
时间复杂度:O( N l o g N NlogN NlogN) , 排序的时间复杂度近似为 N l o g N NlogN NlogN, 然后遍历了一遍数组
空间复杂度:O(1), 使用了常数个变量
方法二:哈希表
思路
step1:将数组中的所有元素全部放入到哈希表
step2:然后从1开始遍历哈希表不存在就结束
代码
int minNumberDisappeared(vector<int>& nums) {unordered_map<int, int> hash;for(auto num : nums){hash[num]++;}int res = 1;while(hash[res]) res++;return res;}
复杂度
时间复杂度:O(N) , 遍历了一遍数组,然后遍历了部分哈希表
空间复杂度:O(N) , 使用了哈希表的额外空间
方法三:原地哈希
思路
- 数组长度和值范围:
- 一个长度为 n 的数组可以包含 n 个元素。
- 如果数组中包含从 1 到 n* 的所有正整数,那么这 n* 个元素正好能填满整个数组。
- 最小的缺失正整数:
- 如果数组中包含了所有 1 到 n* 的数,那么下一个正整数就是 n+1。
- 如果数组中缺少某个数,那么这个缺失的数一定在 1 到 n 之间。
- 极端情况:
- 如果数组中的数全部大于 n 或者非正(如 0 或负数),那么最小的缺失正整数就是 1,因为没有任何数在 1 到 n* 之间。
具体做法:
- step 1:我们可以先遍历数组将所有的负数都修改成n+1。
- step 2:然后再遍历数组,每当遇到一个元素绝对值不超过n时,则表示这个元素是1~n中出现的元素,我们可以将这个数值对应的下标里的元素改成负数,相当于每个出现过的正整数,我们把与它值相等的下标都指向一个负数,这就是类似哈希表的实现原理的操作。
- step 3:最后遍历数组的时候碰到的第一个非负数,它的下标就是没有出现的第一个正整数,因为它在之前的过程中没有被修改,说明它这个下标对应的正整数没有出现过。
代码
int minNumberDisappeared(vector<int>& nums) {int n = nums.size();//遍历数组for(int i = 0; i < n; i++) //负数全部记为n+1if(nums[i] <= 0) nums[i] = n + 1;for(int i = 0; i < n; i++)//对于1-n中的数字if(abs(nums[i]) <= n) //这个数字的下标标记为负数nums[abs(nums[i]) - 1] = -1 * abs(nums[abs(nums[i]) - 1]); for(int i = 0; i < n; i++)//找到第一个元素不为负数的下标if(nums[i] > 0)return i + 1;return n + 1;}
复杂度
从代码中可以看到,除了输入数组
nums
之外,算法没有使用额外的存储空间(只用了一些常数空间用于变量i
和n
)。因此空间复杂度主要取决于输入数组。由于算法就地(in-place)修改输入数组
nums
,没有使用任何额外的存储空间,空间复杂度为 �(1)O(1)。总结
- 时间复杂度:O(n)
- 空间复杂度:O(1)