Leetcode 41. 缺失的第一个正数

谁践踏了优雅 2022-09-09 04:53 154阅读 0赞

## 题目重述 ##

给你一个未排序的整数数组 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 \* 105  
\-231 <= nums\[i\] <= 231 - 1

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/first-missing-positive  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 思路 ##

*  缺失的第一个正数一定在`[1,N+1]`范围内，因为最极端的情况就是长度为N的数组，放了`1,2,3,4......N`这样的元素，此时返回N+1,即缺失的第一个正数
 *  把题目给的元素“归位”，即元素1放到0位置，2放到1位置，这样类推，放好之后，从头判断一下，对应下标有没有放对应值，如果没有返回下标+1就是其缺失的第一个正数

## Java实现 ##

class Solution {
        
        public int firstMissingPositive(int[] nums) {
        
          for(int i=0;i<nums.length;i++){
        
              while(nums[i]>0 && nums[i]<=nums.length && nums[nums[i]-1]!=nums[i]){
        
                  int t = nums[nums[i]-1];
                  nums[nums[i]-1] = nums[i];
                  nums[i] = t;
              }
          }
          // 此时 应该为，[-1,1,3,4]
           for(int i=0;i<nums.length;i++){
        
               if(nums[i]!=i+1){
        
                   return i+1;
               }
           }
           return nums.length+1;
        }
    }

发表评论取消回复

表情：

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

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

相关阅读

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

遍历数组，将数组中数字在0至n-1的放在0至n-1的位置从头遍历，第一个i位置上不是i的时候返回i 需要考虑重复元素的情况，故交换元素的时候要加上条件 if( n

谁践踏了优雅/ 2023年08月17日 17:43/ 0 赞/ 120 阅读

相关 leetcode41 缺失的第一个正数

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

Bertha 。/ 2023年06月20日 06:19/ 0 赞/ 32 阅读

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

相关 leetcode41 缺失的第一个正数

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

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

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

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

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