数据结构-第一个丢失的正数

骑猪看日落 2022-05-18 01:44 117阅读 0赞

***【题目来自灰灰考研】***

（**18年408真题**）

Given an unsorted integer array, find the first missing positive integer.

For example,  
Given

\[1,2,0\] return 3

\[3,4,-1,1\] return 2

\[9,4,-1,1\] return 2

Your algorithm should run in***O*(*n*) time** and uses **constant space**.

#include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<cstdlib> 
    #define MAX 0x3f3f3f3f
    #define MIN 0xc0c0c0c0
    using namespace std;
    
    int findFirstMissingPositive(int data[], int n)
    {
    	/*
    		将给定的合法元素放在正确的位置
    		index:	0	1	2	3	4
    		data: 	1	2	3	4	5
    		如上所示，这是一个标准的在1-n不缺失元素的数组
    		如果给定数组如下
    		index:	0	1	2	3
    		data:	3	4	-1	1
    		那么最终应该调整成：
    		index: 	0	1	2	3
    		data:	1	-1	3	4 
    		
    		最后遍历数组，如果不满足data[i] = i + 1，则返回i + 1
    		若到最后一个元素了还是满足的话，就是最理想的情况，返回n+1即可 
    	*/
    	int i;
    	if(n == 0)
    		return 0;
    	for(i = 0; i < n; i++)
    	{
    		while(data[i] >= 0 && data[i] < n && data[data[i] - 1] != data[i])
    		{
    			int tmp = data[data[i] - 1];
    			data[data[i] - 1] = data[i];
    			data[i] = tmp;
    		}
    	}
    	for(i = 0; i < n; i++)
    	{
    		if(data[i] != i + 1)
    			return i + 1;
    	}
    	return n + 1;
    }
    
    int main()
    {
    	int data[] = {3, 4, -1, 1};
    	int result = findFirstMissingPositive(data, 4);
    	cout<<"The Result is: "<<result<<endl;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，117人围观）

还没有评论，来说两句吧...

相关阅读

相关 41. 缺失的第一个正数

题目： [41. 缺失的第一个正数][41.] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_t

￡神魔★判官ぃ/ 2022年12月07日 12:43/ 0 赞/ 131 阅读

相关 41. 缺失的第一个正数

[https://leetcode-cn.com/problems/first-missing-positive/][https_leetcode-cn.com_problem

我不是女神ヾ/ 2022年09月09日 10:58/ 0 赞/ 157 阅读

相关 Leetcode 41. 缺失的第一个正数

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

谁践踏了优雅/ 2022年09月09日 04:53/ 0 赞/ 116 阅读

相关数据结构-第一个丢失的正数

【题目来自灰灰考研】（18年408真题） Given an unsorted integer array, find the first missing positive

骑猪看日落/ 2022年05月18日 01:44/ 0 赞/ 118 阅读

相关 leetcode:41. 缺失的第一个正数

题目: 给定一个未排序的整数数组，找出其中没有出现的最小的正整数。示例 1: 输入: \[1,2,0\] 输出: 3 示例 2: 输入: \[3,4,-1

向右看齐/ 2022年04月13日 06:40/ 0 赞/ 152 阅读

相关 leetcode:41.缺失的第一个正数

题目描述：给定一个未排序的整数数组，找出其中没有出现的最小的正整数。示例1：输入: [1,2,0] 输出: 3 示例2：输

短命女/ 2022年02月15日 05:21/ 0 赞/ 153 阅读

相关 LeetCode-41.缺失的第一个正数

题目给定一个未排序的整数数组，找出其中没有出现的最小的正整数。示例 1: > 输入: \[1,2,0\] > 输出: 3 示例 2: > 输入:

旧城等待，/ 2022年01月26日 00:37/ 0 赞/ 195 阅读

相关缺失的第一个正数

题目描述给定一个未排序的整数数组，找出其中没有出现的最小的正整数。示例 1: 输入: [1,2,0] 输出: 3 示例 2: 输入:

r囧r小猫/ 2021年12月20日 07:53/ 0 赞/ 178 阅读

相关 leetcode41 缺失的第一个正数

问题描述 1. leetcode41 寻找数组中缺失的第一个正数。 2. 第一个指的是按照数字顺序，在数组中没有出现的正整数要求 1. 时间复杂度O(

川长思鸟来/ 2021年12月03日 23:15/ 0 赞/ 195 阅读

相关 41. 缺失的第一个正数

给定一个未排序的整数数组，找出其中没有出现的最小的正整数。示例 1: > 输入: \[1,2,0\] > 输出: 3 示例 2: > 输入: \[3,4,-1,

小灰灰/ 2021年06月10日 20:37/ 0 赞/ 331 阅读