【LeetCode每日一题】——41.缺失的第一个正数

一【题目类别】

• 哈希表

二【题目难度】

• 困难

三【题目编号】

• 41.缺失的第一个正数

四【题目描述】

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

五【题目示例】

• 示例 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\ast 10^5$
• $-2^{31}<=nums[i]<=2^{31}-1$

七【解题思路】

• 对数组中的元素进行“原地哈希”，第i个元素映射到i-1的位置
• 这样，对于1-N中的元素，如果没有空缺，那么缺失的第一个正数一定是N+1；如果有空缺，那么缺失的第一个整数一定在1-N中
• 然后我们遍历数组，对于映射不匹配的元素直接返回即可

八【时间频度】

• 时间复杂度：$O(n)$，$n$为传入的数组的长度
• 空间复杂度：$O(1)$

九【代码实现】

1. Java语言版

class Solution {public int firstMissingPositive(int[] nums) {int n = nums.length;for(int i = 0;i < n;i++){while(0 < nums[i] && nums[i] <= n && nums[nums[i] - 1] != nums[i]){swap(nums, nums[i] - 1, i);}}for(int i = 0;i < n;i++){if(nums[i] != i + 1){return i + 1;}}return n + 1;}public void swap(int[] nums, int index1, int index2){int temp = nums[index1];nums[index1] = nums[index2];nums[index2] = temp;}
}

2. C语言版

void swap(int* nums, int index1, int index2)
{int temp = nums[index1];nums[index1] = nums[index2];nums[index2] = temp;
}int firstMissingPositive(int* nums, int numsSize)
{int n = numsSize;for(int i = 0;i < n;i++){while(0 < nums[i] && nums[i] <= n && nums[nums[i] - 1] != nums[i]){swap(nums, nums[i] - 1, i);}}for(int i = 0;i < n;i++){if(i + 1 != nums[i]){return i + 1;}}return n + 1;
}

3. Python语言版

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

4. C++语言版

class Solution {
public:int firstMissingPositive(vector<int>& nums) {int n = nums.size();for(int i = 0;i < n;i++){while(0 < nums[i] && nums[i] <= n && nums[nums[i] - 1] != nums[i]){swap(nums, nums[i] - 1, i);}}for(int i = 0;i < n;i++){if(nums[i] != i + 1){return i + 1;}}return n + 1;}void swap(vector<int>& nums, int index1, int index2){int temp = nums[index1];nums[index1] = nums[index2];nums[index2] = temp;}
};

十【提交结果】

1. Java语言版
   

2. C语言版
   

3. Python语言版
   

4. C++语言版