Rechercher des nombres manquants dans le tableau

Question

J'essaie de trouver chaque nombre manquant dans un tableau comme suit.

Array ( 
    [0] => 1 [1] => 2 [2] => 3 [3] => 4 [4] => 5 [5] => 6 [6] => 7 [7] => 8 
    [8] => 9 [9] => 10 [10] => 11 [11] => 12 [12] => 13 [13] => 14 [14] => 15 
    [15] => 16 [16] => 17 [17] => 18 [18] => 19 [19] => 20 [20] => 21 [21] => 22 
    [22] => 23 [23] => 24 [24] => 25 [25] => 26 [26] => 27 [27] => 28 [28] => 29 
    [29] => 30 [30] => 31 [31] => 32 [32] => 33 [33] => 34 [34] => 35 [35] => 36 
    [36] => 37 [37] => 38 [38] => 39 [39] => 40 [40] => 41 [41] => 42 [42] => 43 
    [43] => 44 [44] => 45 [45] => 46 [46] => 47 [47] => 48 [48] => 49 [49] => 50 
    [50] => 51 [51] => 52 [52] => 53 [53] => 54 [54] => 55 [55] => 56 [56] => 57 
    [57] => 58 [58] => 59 [59] => 60 [60] => 61 [61] => 62 [62] => 63 [63] => 64 
    [64] => 67 [65] => 68 [66] => 69 
) 

Les numéros 65, 66 manquent dans ce tableau particulier.

Ma question comment puis-je savoir quels sont les numéros qui manquent avec l'aide de PHP. Plus précisément, ce que j'ai besoin de savoir, c'est le nombre manquant le plus bas. Pourquoi: Parce que je peux alors attribuer ce numéro à un membre en tant qu'identificateur.

Answer 1

Vous pouvez utiliser array_diff et range fonctions:

// given array. 3 and 6 are missing. 
$arr1 = array(1,2,4,5,7); 

// construct a new array:1,2....max(given array). 
$arr2 = range(1,max($arr1));              

// use array_diff to get the missing elements 
$missing = array_diff($arr2,$arr1); // (3,6) 

Answer 2

Je suppose que le nombre est l'élément, pas la clé, du tableau. Je suppose aussi que les chiffres commencent à partir de 1, et non 0.

$Expected = 1; 
foreach ($InputArray as $Key => $Number) 
{ 
    if ($Expected != $Number) 
    { 
     break; 
    } 
    $Expected++; 
} 

echo $Number; 

Answer 3

//$idArrayMissing = array([0] => 1, [1] => 2, [2] => 4, [3] => 5, [4] => 6, [5] => 7); 
$idArrayMissing = array(1, 2, 4, 5, 6, 7); 

//$idArrayFull = array([0] => 1, [1] => 2, [2] => 3, [3] => 4, [4] => 5, [5] => 6); 
$idArrayFull = array(1, 2, 3, 4, 5, 6); 

function gap($arr) 
{ 
    while (list($k, $v) = each($arr)) 
     if ($k != ($v-1)) 
     return $k; 
    return -1; 
} 

print "ok:" . gap($idArrayMissing) . "<br/>\n"; 
print "full:" . gap($idArrayFull) . "<br/>\n"; 

Le retour de la fonction de l'écart peut être 2 valeurs: -1 pourrait indiquer que le tableau a été traversé et il y a pas d'emplacements libres ou $ k + 1 qui pourrait indiquer que le premier emplacement libre se trouve à la fin de la matrice.

Answer 4

Pour les grands tableaux triés de nombres uniques, vous pouvez effectuer une recherche binaire dans le tableau pour le nombre inutilisé le plus bas ou le plus élevé. Coût = Log2N. Exemple: 65536 articles peuvent être recherchés dans 16 boucles depuis

if (arr[hi] - arr[lo] > hi - lo) 
    ... there are unused numbers in that range ... 

Alors (je ne sais pas PHP, mais il peut être traduit ...):

lo = first entry index 
hi = last entry index 
if (arr[hi] - arr[lo] == hi - lo) 
    return arr[hi]+1; // no gaps so return highest + 1 
do 
    { 
    mid = (lo + hi)/2; 
    if (arr[mid] - arr[lo] > mid - lo) // there is a gap in the bottom half somewhere 
    hi = mid; // search the bottom half 
    else 
    lo = mid; // search the top half 
    } while (hi > lo + 1); // search until 2 left 
return arr[lo]+1; 

Answer 5

Il peut aussi se faire facilement en utilisant in_array() function comme ceci:

// lets say $InputArray has all the data 
// lets declare a variable which we will search inside the $InputArray array and lets initialize it with either 0 or 1 or with the minimum value found inside $InputArray 

$start_counting = 1; 
$max_value = count($InputArray); 
    if (!(in_array($start_counting, $InputArray))) 
    { 
     echo "Value: ".$start_counting." is missing!"."<br>" ; 
    } 
else{ 
    if($start_counting <= $max_value -1)  
     {$start_counting++;} 
    } 
    else if($start_counting > $max_value -1) 
    { 
     echo "All missing numbers printed!" 
    } 
}