41. First Missing Positive

public class Solution {
    public int FirstMissingPositive(int[] nums) {
        int n = nums.Length;
        bool[] seen = new bool[n + 1];
        
        foreach (int num in nums) {
            if (num > 0 && num <= n) {
                seen[num] = true;
            }
        }
        for (int i = 1; i <= n; i++) {
            if (!seen[i]) {
                return i;
            }
        }
        return n + 1;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int FirstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        bool[] seen = new bool[n + 1];
        
        foreach (int num in nums) {
            if (num > 0 && num <= n) {
                seen[num] = true;
            }
        }
        for (int i = 1; i <= n; i++) {
            if (!seen[i]) {
                return i;
            }
        }
        return n + 1;
    }
}

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        boolean[] seen = new boolean[n + 1];

        for (int num : nums) {
            if (num > 0 && num <= n) {
                seen[num] = true;
            }
        }

        for (int i = 1; i <= n; i++) {
            if (!seen[i]) {
                return i;
            }
        }

        return n + 1;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var firstMissingPositive = function(nums) {
    const n = nums.length
    const n1 = n + 1
    for (let i = 0; i < n; i++) 
        if (nums[i] <= 0 || nums[i] > n)
            nums[i] = n1
    for (let num of nums) {
        i = Math.abs(num) - 1
        if (i < n && nums[i] > 0)
            nums[i] *= -1
    }
    for (let i = 0; i < n; i++) 
        if (nums[i] > 0)
            return i + 1
    return n1  
};

class Solution:
    def firstMissingPositive(self, nums):
        n = len(nums)
        seen = [False] * (n + 1)

        for num in nums:
            if 0 < num <= n:
                seen[num] = True

        for i in range(1, n + 1):
            if not seen[i]:
                return i

        return n + 1

func firstMissingPositive(nums []int) int {
    n := len(nums)
    seen := make([]bool, n+1)
    
    for _, num := range nums {
        if num > 0 && num <= n {
            seen[num] = true
        }
    }

    for i := 1; i <= n; i++ {
        if !seen[i] {
            return i
        }
    }

    return n + 1
}

Algorithm

Пример:

Input: nums = [3,4,-1,1]

Output: 2

Explanation: 1 is in the array but 2 is missing.

👨‍💻

Алгоритм:

1️⃣

Инициализировать переменную n длиной массива nums. Создать массив seen размером n + 1. Отметить элементы в массиве nums как просмотренные в массиве seen.

Для каждого числа num в массиве nums, если num больше 0 и меньше или равно n, установить seen[num] в значение true.

2️⃣

Найти наименьшее недостающее положительное число:

Проитерировать от 1 до n, и если seen[i] не равно true, вернуть i как наименьшее недостающее положительное число.

3️⃣

Если массив seen содержит все элементы от 1 до n, вернуть n + 1 как наименьшее недостающее положительное число.

😎