题解 | #缺失的第一个正整数#
缺失的第一个正整数
http://www.nowcoder.com/practice/50ec6a5b0e4e45348544348278cdcee5
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @return int整型
*/
int minNumberDisappeared(vector<int>& nums) {
int n = nums.size();
for(int i=0; i<nums.size(); i++){
while(nums[i]>0 && nums[i] <=n && nums[i] != nums[nums[i]-1]){
swap(nums[i], nums[nums[i]-1]);
}
}
for(int i=0; i<n; i++){
if(nums[i] != i+1)
return i+1;
}
return n+1;
// write code here
}
};
(数组,哈希表,原地交换)
如果没有空间限制的话，可以使用哈希表来解，先把所有元素放入哈希表 set 中，然后从 1 开始在哈希表中查询第一个未出现的正整数。
要求使用常数空间的话想到在原数组原地交换，而我们关心的是正数，所以如果 nums[i] 是正数 > 0 且 < n 且 nums[i] 的位置上不是当前数，就把他放到应该的位置上去（防止死循环，如果原来就在正确的位置上，一直交换）
每个正数 nums[i] 的位置在 nums[i] - 1 上，即 0 的位置上放 1，以此类推（因为数组的大小是 n，那如果出现 n 放在位置 n 上会越界）。
最后再遍历一遍数组，如果当前位置上的数 nums[i] 不等于 i + 1，则 i + 1 就是缺少的正整数。
如果遍历结束之后，还没有找到答案，说明所有数都在正确的位置上，是一个连续序列，那么答案就是 n + 1。
投递大疆等公司8个岗位