Учитывая массив целых чисел, верните наименьшее положительное целое, а не в него

  

Напишите функцию:

function solution(A);
     

, что, учитывая массив A целых чисел N, возвращает наименьший положительный результат   целое число (больше 0), которое не встречается в A.

     

Например, при заданном A = [1, 3, 6, 4, 1, 2] функция должна возвращаться   5.

     

Учитывая A = [1, 2, 3], функция должна вернуть 4.

     

Учитывая A = [−1, −3], функция должна вернуть 1.

     

Предположим, что:

     
  • N - целое число в диапазоне [1..100.000]
  •   
  • Каждый элемент массива A является целым числом в диапазоне [â'1,000,000..1,000,000]
  •   

Сложность:

     
  • Ожидаемая наихудшая временная сложность - \ $ O (N) \ $
  •   
  • Ожидаемая наихудшая пространственная сложность - \ $ O (N) \ $, за пределами входного хранилища (не считая хранения, необходимого для входных аргументов)
  •   

Элементы входных массивов могут быть изменены.

Решение в \ $ O (n ^ 2) \ $:

function solution(A) {
  for (i = 1; i < 1000000; i++) {
    if(!A.includes(i)) return i;
  }
}
27 голосов | спросил Philip Kirkbride 28 +03002017-10-28T21:33:30+03:00312017bEurope/MoscowSat, 28 Oct 2017 21:33:30 +0300 2017, 21:33:30

10 ответов


22

Это приятное простое решение с двумя проблемами:

  1. Он даст неверный результат, если A содержит все значения в диапазонах [1..1000000] или [1..999999], возвращая undefined вместо 1000001 и 1000000 соответственно.
  2. Это не соответствует требованию временной сложности, будучи \ $ O (n ^ 2) \ $ вместо \ $ O (n) \ $.

Первая проблема легко исправить, отрегулировав конечное условие цикла.

Вторая проблема сложнее, и интересная часть упражнения. Рассмотрим этот алгоритм: \ $ O (n) \ $ во времени и \ $ O (1) \ $ в пространстве:

  • Прокрутите элементы A с самого начала и для каждого значения A[i], если A[i] - 1 является допустимым индексом в массиве, затем повторно меняет A[i] и A[A[i] - 1] до A[i] находится в правильном месте (значение равно i + 1) или A[i] и A[A[i] - 1] равны.
    • Это должно упорядочить значения в их правильных местах таким образом, чтобы A[i] == i + 1, когда это возможно
  • Повторите цикл над элементами, чтобы найти индекс, где A[i] != i + 1, если существует, то отсутствующее значение: i + 1
  • Если конец цикла достигнут без возврата значения, то отсутствующее значение будет A.length + 1.

Вот один из способов реализации этого в JavaScript:

var firstMissingPositive = function(nums) {
    var swap = function(i, j) {
        var tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    };

    for (let i = 0; i < nums.length; i++) {
        while (0 < nums[i] && nums[i] - 1 < nums.length
                && nums[i] != i + 1
                && nums[i] != nums[nums[i] - 1]) {
            swap(i, nums[i] - 1);
        }
    }

    for (let i = 0; i < nums.length; i++) {
        if (nums[i] != i + 1) {
            return i + 1;
        }
    }
    return nums.length + 1;
};

Примечание. Чтобы проверить это или выполнить альтернативную реализацию, вы можете отправить на лит-код .

ответил janos 28 +03002017-10-28T22:13:47+03:00312017bEurope/MoscowSat, 28 Oct 2017 22:13:47 +0300 2017, 22:13:47
15

Как насчет этого решения, которое, если я не ошибаюсь, должно отвечать всем требованиям:

  • создать второй массив
  • выполняется через все элементы входного массива
  • для каждого номера задайте соответствующий ключ во втором массиве true
  • пропустите второй массив и верните первый ключ, значение которого возвращается как undefined
  • Если совпадение не найдено, верните 1, поэтому он будет работать и для пустого массива ввода

function findNumber(values) {
  let result = [];

  for (let i = 0; i < values.length; ++i) {
    if (0 <= values[i]) {
      result[values[i]] = true;
    }
  }

  for (let i = 1; i <= result.length; ++i) {
    if (undefined === result[i]) {
      return i;
    }
  }

  return 1
}

Попробуйте сами


Мы с Патриком обсудили эффективность наших решений в режиме реального времени ( элегантное решение Патрика с использованием Set ). Мы установили тест, содержащий около 1000 элементов во входном массиве, включая множество отрицательных значений. Вы можете попробовать тест .

JollyJoker предложил похожую версию в комментариях с использованием встроенного в JavaScript кода filter, reduce и findIndex. Я исправил предлагаемое решение для краевых случаев и добавил его к тесту производительности. Теперь вы можете проверить все три решения . Имейте в виду, что эти встроенные модули поставляются с некоторыми накладными расходами.

Янош добавил код для своего алгоритма, а теперь . Чтобы завершить тест производительности, я добавил его, а вот финальная скрипка, содержащая все четыре решения .

ответил insertusernamehere 29 +03002017-10-29T01:21:13+03:00312017bEurope/MoscowSun, 29 Oct 2017 01:21:13 +0300 2017, 01:21:13
12

Чтобы удовлетворить временную сложность O (N) , постройте Set() в O (N) сложность времени и пространства, а затем использовать while, который считается постоянным временем относительно N O (N) , а также (спасибо , wchargin ), так как максимально возможное количество итераций равно N , а средняя производительность операции Set#has() равна O (1) . Поскольку O (N + N) = O (N) , что касается временной сложности, это решение является общей производительностью O (N) как во времени, так и в пространстве:

function solution(A) {
  const set = new Set(A);
  let i = 1;

  while (set.has(i)) {
    i++;
  }

  return i;
}

Несмотря на то, что это относительно упрощенная и обманчиво элегантная реализация, решение insertusernamehere , по общему признанию, является порядком при использовании массива как идеальной хеш-таблицы для неотрицательных целых чисел.

ответил Patrick Roberts 29 +03002017-10-29T03:37:34+03:00312017bEurope/MoscowSun, 29 Oct 2017 03:37:34 +0300 2017, 03:37:34
3

Следует отметить, сколько места вам разрешено использовать. Вы можете использовать до O(n) пробел (достаточно, чтобы сделать полную копию ваших данных). В настоящее время ваш код медленный, потому что он использует операторы O(n) in, каждый из которых является O(n). Это означает, что если бы существовала только структура данных, на которой in были O(1), вы бы решили свою проблему. К счастью, Set имеет именно это свойство. Таким образом, единственное изменение, которое вам нужно внести в решение, - это превратить ваш list в set.

ответил Oscar Smith 28 +03002017-10-28T23:56:40+03:00312017bEurope/MoscowSat, 28 Oct 2017 23:56:40 +0300 2017, 23:56:40
3

В JavaScript вы можете сделать это:

  1. Сначала упорядочьте свой массив с помощью метода JavaScript Array.sort() со сложностью \ $ O (n \ log (n)) \ $ ( показано здесь ):

    var A=[4,3,2,1,0,-3];
    A.sort(function(a, b){return a-b});
    //returns the array ordered [-3,0,1,2,3,4]
    
  2. Перебирать только упорядоченный массив. Для каждого значения проверьте, больше ли значение больше 0, и если следующий элемент массива не равен текущему значению + 1.

    function(A){
        for(var i=0;i<A.length-1;i++){// iterate until  penultimate element
            if(A[i]>0 && A[i+1]!=(A[i]+1)){
                return (A[i]+1);
            }
        }
    }
    
ответил havelino 29 +03002017-10-29T03:28:56+03:00312017bEurope/MoscowSun, 29 Oct 2017 03:28:56 +0300 2017, 03:28:56
2
function solution(A) {
  for (i = 1; i < 1000000; i++) {
    if(!A.includes(i)) return i;
  }
}

Будьте в соответствии с вашим интервалом. Вы используете пробел после for, но не для if. Пространство помогает разделить языковые конструкции на вызовы функций.

Для языков, которые используют фигурные скобки, всегда привязывайте свои однострочные (явно устанавливайте границу цикла) и предпочитайте иметь их на отдельной строке для удобства чтения, обслуживания и отладки (точки останова!).

Что произойдет, если len(A) >= 1,000,000? Используйте длину массива вместо произвольного значения. См. Ниже.


Вы можете упростить эту проблему, фильтруя /разбивая любое неположительное значение из массива. После того, как у вас есть фильтрованный массив положительных целых чисел, вы можете использовать отфильтрованную длину, чтобы определить верхнюю границу наименьшего положительного целого числа. Для отличной последовательности целых чисел \ $ D = [1, 2, 3, ..., n] \ $ наименьшее положительное целое гарантируется как \ $ n + 1 \ $. Если вы удаляете любое значение из \ $ D \ $ и заменяете его любым значением другого (или просто удаляете его), то младшее положительное целое число \ $ D \ $ находится в диапазоне \ $ [ 1, n] \ $. Чтобы найти его, мы можем просто отслеживать целые числа в булевой таблице, до \ $ n \ $, отмечая свидетелей. Линейный поиск булевского массива для первой немаркированной записи даст нам нулевой индекс наименьшего положительного целого числа. Добавьте один, чтобы сделать его один на один раз. Фильтрация, маркировка свидетелей и поиск - все линейные операции.

Примечание . Поскольку вы знаете верхнюю границу, вы можете сузить свой диапазон дальше, сделав второй проход фильтра, который удаляет любые элементы, превышающие длину массива. Помогла бы с местоположением данных, если у вас есть небольшие массивы, загруженные довольно большими значениями.

В то время как использование логического массива удовлетворяет требованиям к пространственной сложности, существует постоянное пространственное решение. Помните, что каждый элемент в вашем фильтрованном массиве положителен, поэтому мы можем перепрограммировать бит знака каждого значения в качестве сигнала, свидетельствующего о значении последовательности. Мы можем использовать индексы фильтрованного массива так же, как мы делали выше булевой массив. Вместо поиска первого элемента, помеченного как false (неясно), мы ищем первое значение, которое все еще положительно.

solution(A)
    Filter non-positive values from A
    For each int in filtered
        Let a zero-based index be the absolute value of the int - 1
        If the filtered range can be accessed by that index
            Make the value in filtered[index] negative
    For each index in filtered
        if filtered[index] is positive, return the index + 1 (to one-based)
    otherwise return the length of filtered + 1 (to one-based)

Итак, массив \ $ A = [1, 2, 3, 5, 6] \ $ будет иметь следующие преобразования:

abs(A[0]) = 1, to_0idx = 0, A[0] = 1, make_negative(A[0]), A = [-1,  2,  3,  5,  6]
abs(A[1]) = 2, to_0idx = 1, A[1] = 2, make_negative(A[1]), A = [-1, -2,  3,  5,  6]
abs(A[2]) = 3, to_0idx = 2, A[2] = 3, make_negative(A[2]), A = [-1, -2, -3,  5,  6]
abs(A[3]) = 5, to_0idx = 4, A[4] = 6, make_negative(A[4]), A = [-1, -2, -3,  5, -6]
abs(A[4]) = 6, to_0idx = 5, A[5] is inaccessible,          A = [-1, -2, -3,  5, -6]

Линейный поиск первого положительного значения возвращает индекс 3. Преобразование обратно в однонаправленный индекс приводит к решению \ $ (A) = 3 + 1 = 4 \ $

ответил Snowhawk 29 +03002017-10-29T16:43:25+03:00312017bEurope/MoscowSun, 29 Oct 2017 16:43:25 +0300 2017, 16:43:25
2

Вы можете тривиально найти более быстрое решение, чем тот, который вы уже дали, просто сначала отсортировав массив, разделив все неположительные целые числа и начните поиск оттуда - это делает алгоритм an \ $ O (n \ log n) \ $ в худшем случае и в лучшем случае a \ $ O (n) \ $ алгоритм и не требует дополнительного пространства.

В качестве альтернативы просто добавьте все положительные числа в набор и найдите наименьшее положительное число, которое не находится в этом наборе. Если вы хотите сделать это меньше, чем \ $ O (n \ log n) \ $ time, вам нужно использовать битвектор; пройдите все элементы и установите бит n в векторе true, когда проверяемый элемент равен n. Это займет пространство \ $ O (n) \ $ time и \ $ O (n) \ $.

Чтобы получить размер битового вектора, просто найдите наибольшее целое число (и самое маленькое, когда вы на нем), и выделите это множество бит. Это также можно сделать в \ $ O (n) \ $ time. Если наименьшее целое число не равно 1, то число, которое вы ищете , равно 1.

ответил Clearer 29 +03002017-10-29T21:10:52+03:00312017bEurope/MoscowSun, 29 Oct 2017 21:10:52 +0300 2017, 21:10:52
1

Использование set делает проблему O (N lg N) в качестве связанных каталогов lg N для каждой вставки, удаления и поиска. Если вы не используете хеш-версию связанных каталогов, в этом случае вы не можете найти следующий в O (1), так как наихудший вариант - O (N).

Сортировка с функцией сравнения всегда приводит к O (N lg N), но другие специализированные сортировки не относятся к сортировке.

Таким образом, мы могли бы попробовать специализацию подсчета сортировки, назовем ее видом существования, поскольку нам не интересно, сколько, но только в том случае, если оно существует.

Далее мы обрезаем диапазон чисел в исходном массиве только с включенными значениями от 1 до 100000.

Псевдокод для этого метода:

min = 1
max = 100000

bool num[100000] = false // 100000 long array of bool, add 1 (one) if your language array index start at 0 (zero)


for (i = 1; i < 1000000; i++) {
  can = A[i];
  if(can >= min && can <= max) {
    num[can] = true;    // register numbers that exist in our range
  }
}

for (i = min; i <= max; i++)
  if (!num[i])
    return i;
ответил Surt 29 +03002017-10-29T10:51:02+03:00312017bEurope/MoscowSun, 29 Oct 2017 10:51:02 +0300 2017, 10:51:02
1

Вот PHP-решение (начальный тест):

<?php
$a = array(
    2, 1, 3, 5, 6, 7,
);

function solution(array $a = array()){
    /**
     * Assumes that the first positive integer
     * in an empty array will be 1 - also stops
     * potential for infinite loop in while()
     * below
     */
    if(!count($a)){
        return 1;
    }

    $i = 0;

    while(in_array(++$i, $a)){}

    return $i;
}

echo solution($a);

и здесь находится рефакторизованная версия, основанная на обратной связи в комментариях ниже:

function solution(array $a = array()){
    /**
     * Assumes that the first positive integer
     * in an empty array will be 1 - also stops
     * potential for infinite loop in while()
     * below
     */
    if(!count($a)){
        return 1;
    }

    /**
     * Lowest possible number in set
     * -1 so it starts counting at
     * -1000000
     */
    $i =-1000001;
    $c = 1;

    while($c){
        $i++;
        if(($i > 0 && !in_array($i, $a)) || $i > 1000000){
            $c = 0;
        }
    }

    /**
     * If $i is negative, the lowest positive
     * integer in set will be 1, otherwise it
     * will be the set value of $i unless $i
     * is out of range for this task
     */
    if($i <= 1000000){
        return ($i < 1) ? 1 : $i;
    }
    return 'Value out of range';
}
ответил Shaun Bebbers 1 32017vEurope/Moscow11bEurope/MoscowWed, 01 Nov 2017 20:12:45 +0300 2017, 20:12:45
1

Следующее решение в Java должно быть в пределах границ времени и пространства:

public int solution(int[] A)
{
    java.util.HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(A.length); //O(n) space
    for (int i : A) // O(N)
    {
        if (!map.containsKey(i))
        {
            map.put(i, i);
        }
    }
    int smallestPositive = 1;
    for (int i = 1; i < 1000001; i++) // ~O(N)
    {
        if (map.containsKey(i) && map.get(i) <= smallestPositive)
        {
            smallestPositive = map.get(i) + 1;
        }
    }
    return smallestPositive;
}

Я собирался написать, что вы могли бы даже протолкнуть HashMap и перебрать A во втором цикле, поскольку 1,000,000 является константой и должно быть незначительным, но выглядит как они конкретно задали вопрос в вопросе о том, что \ $ N \ $ составляет 100 000, что меньше, поэтому вы можете считать, что второй цикл имеет значение \ $ O (n) \ $ time.

Он суммирует до \ $ O (n) + O (n) = O (n) \ $ time и \ $ O (n) \ $ пространство для отображения.

ответил Dopefish 27 Jam1000000amSat, 27 Jan 2018 03:51:35 +030018 2018, 03:51:35

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132