給你一個(gè)未排序的整數(shù)數(shù)組，請(qǐng)你找出其中沒有出現(xiàn)的最小的正整數(shù)。

示例 1:

輸入: [1,2,0]
輸出: 3
示例 2:

輸入: [3,4,-1,1]
輸出: 2
示例 3:

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

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/first-missing-positive

解題思路

先遍歷數(shù)組, 試圖將元素1放在位置0, 元素2放在位置1, ...以此類推
忽略負(fù)數(shù)和超過數(shù)組長度的數(shù)
調(diào)整完數(shù)組后, 遍歷數(shù)組, 找出第一個(gè)不符合"元素值 = 索引 + 1"的即為答案
如果全都滿足則直接返回?cái)?shù)組長度 + 1
nums[i] != nums[nums[i] - 1] 判斷某元素是否在該元素 - 1對(duì)應(yīng)的位置
也就是元素 1 是否在位置 0, 元素 2 是否在位置 1

代碼

class Solution {
    public int firstMissingPositive(int[] nums) {
        // 遍歷數(shù)組
        for (int i = 0; i < nums.length; i++) {
            // 試圖將元素1放在位置0, 元素2放在位置1, ...以此類推
            // 忽略負(fù)數(shù)和超過數(shù)組長度的數(shù)
            while (nums[i] > 0 && nums[i] <= nums.length && nums[i] != nums[nums[i] - 1]) {
                swap(nums, i, nums[i] - 1);
            }
        }
        // 調(diào)整完數(shù)組后, 遍歷數(shù)組, 找出第一個(gè)不符合"元素值 = 索引 + 1"的即為答案
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        // 如果全都滿足則直接返回?cái)?shù)組長度 + 1
        return nums.length + 1;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}