Geek Answers Handbook

Search for the first integer not used in a set of integers

After extracting the list of integers used for the ID in the mysql database, taking into account that all identifiers do not follow each other in each case (for example, the list can be [1,2,3,5,10,11, 12, 20, ...]), which would be a more efficient way, except for scrolling through all integers, to find the smallest integer that is not yet on the list (in our case it would be 4, then 6 times 4). Also, it should not be higher than 999.

This question gives a mysql query, but I would like to do this in my php script, unless it will be more efficient.

+5
source share
6 answers

This problem can be solved easily and efficiently using binary search (which works in O (log n), faster than linear search, which is O (n)). The basic idea is that if and only if all numbers are present up to a certain index, then the list [index] = index + 1 (for example, list [0] = 1, list [1] = 2, etc. ) This property can be used to determine if the smallest missing number is before or after a specific list item, which allows you to perform a binary search.

The implementation is simple (I don't know php, so here's the pseudocode)

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

And missing_numberwill be the smallest missing number, or if there will be missing numbers length(list) + 1.

Or using the recursion I hear is less efficient

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

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;
}
+5

:

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

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
)
0

, :

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

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.

0
$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.
0

More articles:


All Articles