【原】LeetCode实战：缺失的第一个正数

老马的程序人生 2020-08-17

展开全文

题目英文

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

Example 1:

Input: [1,2,0]
Output: 3

Example 2:

Input: [3,4,-1,1]
Output: 2

Example 3:

Input: [7,8,9,11,12]
Output: 1

Note:

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

题目中文

给定一个未排序的整数数组，找出其中没有出现的最小的正整数。

示例1:

输入: [1,2,0]
输出: 3

示例2:

输入: [3,4,-1,1]
输出: 2

示例3:

输入: [7,8,9,11,12]
输出: 1

示例4:

输入: [1,1]
输出: 2

实例5:

输入: []
输出: 1

说明:

你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。

算法实现

// 把数组进行一次“排序”，
// “排序”的规则是：如果这个数字 i 落在“区间范围里”，i 就应该放在索引为 i - 1 的位置上。
public class Solution {
    public int FirstMissingPositive(int[] nums) {
        int len = nums.Length;
        for (int i = 0; i < len; i++)
        {
            while (nums[i] != i + 1 && nums[i] <= len && nums[i] > 0 && nums[i] != nums[nums[i] - 1])
            {
                int temp = nums[i];
                nums[i] = nums[temp - 1];
                nums[temp - 1] = temp;
            }
        }
        for (int i = 0; i < len; i++)
        {
            if (nums[i] != i + 1)
            {
                return i + 1;
            }
        }
        return len + 1; //nums.Length = 0        
    }
}