Нахождение первого целого числа, не используемого в коллекции целых чисел

Question

После получения списка целых чисел, используемых для идентификатора, в базе данных mysql, принимая во внимание, что все идентификаторы не следуют друг за другом в каждом случае (например, список может быть [1,2,3,5,10,11 , 12,20, ...]), что было бы более эффективным способом, кроме циклического перебора всех целых чисел, найти наименьшее целое число, которого еще нет в списке (в нашем случае это было бы 4, потом 6 раз 4 приписывается). Также оно не должно быть выше 999.

Этот вопрос дает запрос mysql, но я хотел бы сделать это в своем php-скрипте, кроме случаев, когда он будет более эффективным.

Answer 1

Эта проблема может быть легко и эффективно решена с помощью двоичного поиска (который выполняется в O (log n), быстрее, чем линейный поиск, который является O (n)).Основная идея заключается в том, что если и только если все числа присутствуют до определенного индекса, то list [index] = index + 1 (например, list [0] = 1, list [1] = 2 и т. Д.).Это свойство может использоваться для определения того, находится ли наименьшее пропущенное число до или после определенного элемента списка, что позволяет выполнять двоичный поиск.

Реализация проста (я не знаю php, так что вот псевдокод)

lower_bound = 0
upper_bound = length(list) - 1
index = floor((lower_bound + upper_bound) / 2)
while (lower_bound != upper_bound)  
     if(list[index] = index + 1)     // missing number is after index
          lower_bound = index + 1
          index = floor((lower_bound + upper_bound) / 2)
     else                            // missing number is at or before index
          upper_bound = index
          index = floor((lower_bound + upper_bound) / 2)
missing_number = upper_bound + 1     // add 1 because upper_bound is the index

И missing_number будет наименьшим пропущенным числом, или если пропущенных чисел нетбудет length(list) + 1.

---

или с использованием рекурсии, которая, как я слышал, менее эффективна

first_missing_number(list, lower_bound, upper_bound) {
     if(lower_bound = upper_bound)  // found the first missing number
          return upper_bound + 1    // add 1 because upper_bound is the index
     index = floor((lower_bound + upper_bound) / 2)
     if (list[index] = index + 1)   // missing number is after index
          first_missing_number(list, index + 1, upper_bound)
     else                           // missing number is at or before index
          first_missing_number(list, lower_bound, index)
}

В этом случае first_missing_number(list, 0, length(list) - 1) вернет первый номер, отсутствующий в списке.Если пропущенные цифры отсутствуют, возвращается length(list) + 1.

Надеюсь, это поможет!

upd: php version

function first_free($list) {
    $lwr = 0;
    $upr = count($list);

    while ($lwr < $upr) { 
        $m = ($lwr + $upr) >> 1;
        if($list[$m] == $m + 1)
            $lwr = $m + 1;
        else
            $upr = $m;
    }
    return $upr + 1;
}

Answer 2

наиболее эффективным способом является простой цикл:

foreach($list as $n => $v)
   if($v !== $n + 1) return $n + 1;

Answer 3

$array   = array(1,2,3,5,10,11,12,20);
$missing = array_diff(range(min($array), max($array)), $array);

// First missing number is at $missing[0], next at $missing[1], etc.

Answer 4

Поскольку вы ограничены только 999 возможными ключами, я бы, вероятно, создал временную таблицу со всеми возможными ключами (например, 1-999) или даже создал бы постоянную таблицу только для этой цели, тогда вы можете сделать sql следующим образом :

SELECT key_value FROM temp_key_table WHERE key_value NOT IN (SELECT key FROM original_table ORDER BY key ASC) ORDER BY key_value ASC LIMIT 1

Не уверен, насколько это практично, и SQL-гуру, вероятно, мог бы дать вам лучшее решение, но это должно работать в крайнем случае, а не возиться с этим в PHP.

Answer 5

Может быть, это будет более эффективным способом:

$your_list = array(....);
$number_you_want = min(array_diff(range(1,999), $your_list));

Answer 6

Вы можете использовать функцию array_diff():

например:

<?php
$array1 = array("a" => "1", "2", "3", "4");
$array2 = array("b" => "2", "4");
$result = array_diff($array1, $array2);

print_r($result);
?>

это даст вам недостающие элементы во втором массиве:

Array
(
    [1] => 1
    [2] => 3
)