Сведения о проблеме

  • Эта проблема была задана Stripe.
  • Учитывая массив целых чисел, найдите первое пропущенное положительное целое число в линейном времени и постоянном пространстве. Другими словами, найдите наименьшее положительное целое число, не существующее в массиве. Массив также может содержать дубликаты и отрицательные числа.
  • Например, ввод [3, 4, -1, 1] должен дать 2. Вход [1, 2, 0] должен дать 3.
  • Вы можете изменить входной массив на месте.

Проблема Решение(по объяснению)

Решение 1.

  • Временная сложность: O(n), Пространственная сложность: O(n)
  • Создайте массив размером n + 1 и заполните его 0 (false)

[3, 4, -1, 1] → [0, 0, 0, 0, 0] : массив вхождений, n равно 4

  • Итерация по входному массиву и пометка массива вхождений 1 (истина), если элемент входного массива больше 0 и меньше, чем n

[3, 4, -1, 1] выберите [3] между 0 и 4 → [0, 0, 0, 1, 0]

[3, 4, -1, 1] выберите [4] между 0 и 4 → [0, 0, 0, 1, 1]

[3, 4, -1, 1] выберите [-1] это не между 0 и 4 → [0, 0, 0, 1, 1]

[3, 4, -1, 1] выберите [1] между 0 и 4 → [0, 1, 0, 1, 1]

  • Теперь выполните итерацию по массиву вхождений, начиная с индекса 1 до индекса n, если найдено 0 (false), что является решением

[0, 1, 0, 1, 1] первое появление 0 (ложь) находится в индексе 2, это решение проблемы

Решение 2.

  • Временная сложность: O(n), Пространственная сложность: 1
  • Сначала проверьте, есть ли в массиве 1, если нет, то решение 1
  • Замените отрицательные числа и положительные числа, которые больше n, на 1

[3, 4, -1, 1] n is 4.

[3, 4, -1, 1] → [3, 4, 1, 1]

  • Перебрать результирующий массив и добавить n к элементам, которые соответствуют (arr[i]-1)%n

[3, 4, 1, 1] выбрать 3 добавить 4 к индексу (3–1)%4 [3, 4, 5, 1]

[3, 4, 1, 1] выбрать 4 добавить 4 к индексу (4–1)%4 [3, 4, 5, 5]

[3, 4, 1, 1] выбрать 1 добавить 4 к индексу (1–1)%4 [7, 4, 5, 5]

[3, 4, 1, 1] выбрать 1 добавить 4 к индексу (1–1)%4 [11, 4, 5, 5]

  • Перебрать результирующий массив и найти элемент массива, который меньше или равен n, таким образом, результат (found_index + 1)

[11, 4, 5, 5] → 4 удовлетворяют вышеуказанному условию в индексе 1, и результат равен 2

  • Если до этого момента решения нет, то решение равно n+1, поскольку все значения, меньшие n, существуют в массиве.

Решение проблемы (с помощью js)

// Helper function to print the array with delimiter '-'
function printArray(arr) {
    var s = '';
    for (let i = 0; i < arr.length; i++) {
        if(i==0) {
            s += '(' + my_list[i] + ')';
        }
        else {
            s += '-(' + my_list[i] + ')';
        }
        
    }
    console.log(s);
}

// Time Complexity : O(n)
// Space Complexity : O(n)
function smallestPositiveNumber1(arr) {
    var n = arr.length;
    var occurence = [];

    // Mark the occurence array with false [0, n]
    for(let i=0; i<=n; i++) {
        occurence.push(false);
    }

    // Mark the occurence array with true if the value in [1, n]
    for(let i=0; i<n; i++) {
        if(arr[i]>0 && arr[i]<=n) {
            occurence[arr[i]] = true;
        }
    }

    // Check if the occurence array has false in between [1, n] then
    // it is the solution if not, then the solution will be n+1
    for(let i=1; i<=n; i++) {
        if(occurence[i]==false) {
            return i;
        }
    }

    return n+1;
}

// Time Complexity : O(n)
// Space Complexity : 1
function smallestPositiveNumber2(arr) {
    var isOneInTheArray = false;
    var n = arr.length;

    // First check, if 1 is in the array
    for (let i = 0; i < n; i++) {
        if (arr[i] == 1) {
            isOneInTheArray = true;
            break;
        }
    }

    // if 1 is not in the array then the solution is 1 and return it
    if (!isOneInTheArray) {
        return 1;
    }

    // Replace negative numbers and positive numbers which are 
    // greater then n with 1
    for (let i = 0; i < n; i++) {
        if (arr[i] <= 0 || arr[i] > n) {
            arr[i] = 1;
        }
    }

    // Now in the input array there is only numbers 1 to n
    // Need to find which element is missing
    // For this, add n to each value at index (arr[i]-1)%n
    // This process will mark each value as greater then n if 
    // the value occurs in the array if not the value will be smaller then n
    for (let i = 0; i < n; i++) {
        arr[(arr[i] - 1) % n] += n;
    }

    // Search for the value in the array which is smaller then n
    // then return the index i+1
    for (let i = 0; i < n; i++) {
        if (arr[i] <= n) {
            return i + 1;
        }
    }

    // If there is no solution until here then return the value n+1
    return n + 1;
}

var my_list = [3, 4, -1, 1];
printArray(my_list)
console.log("Result = " + smallestPositiveNumber1(my_list))
console.log("Result = " + smallestPositiveNumber2(my_list))