leetcode 41. 缺失的第一个正数

大耗子 2021年02月19日 11次浏览

题目: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

提示:

  • 0 <= nums.length <= 300
  • -231 <= nums[i] <= 231 - 1

解题思路

使用哈希的方式

将大于0的数据的哈希表位置置为1,从map[1]循环到map[nums.size()+1],第一个为0的位置就是题目需要的正整数。

交换数组数据方式

  • 判断是否为对应位置的值
  • 判断是否为1到size()范围的数值
  • 判断要交换的位置的值,是否已经是对应位置需要的值,例如下标0位置需要1,如果该位置已经是1,那么也不必交换,不判断会死循环交换的(亲身实验)。

满足上诉三个条件就可以交换数组位置数据。

然后循环数组,第一个位置上不匹配的值一定是第一个缺少的正数值。

代码

class Solution {
public:
	int firstMissingPositive(vector<int>& nums) {
		if (!nums.size()) return 1;
		int i = 0;
		for (i = 0; i < nums.size(); i++){
			while (nums[i] != i+1  &&   // 判断是否为对应位置的值
				nums[i] > 0 && nums[i] <= nums.size() &&  // 判断是否为1到size()范围的数值
				// 判断要交换的位置的值,是否已经是对应位置需要的值,例如下标0位置需要1,如果该位置已经是1,那么也不必交换,不判断会死循环交换的
				nums[nums[i] - 1] != nums[i]){
				swap(nums[i], nums[nums[i] - 1]); 
			}
		}
		for (i = 0; i < nums.size(); i++){
			// 第一个位置上不匹配的值一定是第一个缺少的正数值
			if (nums[i] != i+1) {
				return i+1;
			}
		}
		return nums.size()+1;
	}
	void print(vector<int>& nums) {
		for (int i = 0; i < nums.size(); i++)
		{
			cout << nums[i] << "  ";
		}
		cout << endl;
	}
};


void main()
{
	vector<int> nums = { 1, 1};
	Solution sln;
	int ret = sln.firstMissingPositive(nums);
	cout << ret << endl;
}