BM53. [缺失的第一个正整数]
https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295
BM53. 缺失的第一个正整数
题目的主要信息：
- 给定一个无重复元素的整数数组nums
- 找出其中没有出现的最小的正整数
- 要求： 空间复杂度：
，时间复杂度：
方法一：哈希表
具体做法：
可以遍历数组用一个哈希表记录数组中哪些数字出现过，然后从1开始找，找到第一个不在哈希表中出现的数字即可。
class Solution {
public:
int minNumberDisappeared(vector<int>& nums) {
int n = nums.size();
unordered_map<int, int> mp;
for(int i = 0; i < n; i++) //哈希表记录数组中出现的每个数字
mp[nums[i]]++;
int res = 1;
while(mp.find(res) != mp.end()) //从1开始找到哈希表中第一个没有出现的正整数
res++;
return res;
}
};
复杂度分析：
- 时间复杂度：
，单独遍历两次，最坏情况两次都遍历到
- 空间复杂度：
方法二：原地哈希
具体做法：
因为数组n个元素都是不重复的，因此第一个缺失的正整数要么是1-n中的某一个数字，要么就是n+1.
我们可以先遍历数组将所有的负数都修改成n+1，然后遍历数组，每当遇到一个元素绝对值不超过n时，则表示这个元素是1-n中出现的元素，我们可以这个数值对应的下标里的元素改成负数。
这样再次遍历数组的时候碰到的第一个非负数的下标就是没有出现的第一个正整数。
class Solution {
public:
int minNumberDisappeared(vector<int>& nums) {
int n = nums.size();
for(int i = 0; i < n; i++) //遍历数组
if(nums[i] <= 0) //负数全部记为n+1
nums[i] = n + 1;
for(int i = 0; i < n; i++)
if(abs(nums[i] <= n)) //对于1-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;
}
};
复杂度分析：
- 时间复杂度：
- 空间复杂度：
查看6道真题和解析
