在数组中查找缺失的数字

Question

我试图找到类似以下数组中的每个缺失数字。

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 
)

这个特定数组中缺失了数字65和66。

我的问题是如何使用PHP找出缺失的数字。具体而言，我需要找到最小的缺失数字。

为什么：因为我可以把这个数字分配给成员作为ID。

- nickifrandsen

---

我认为这不是获取唯一ID的最佳方式 - 当您有100000000个用户时会发生什么？可能需要一段时间才能找到ID。 - Jeff Foster

@Jeff Foster，如果在任何时候查找id花费了很长时间，显而易见的解决方案是delete users where id > 1000;。这样速度就会再次变快！ :) - acm

Answer 1

你可以使用 array_diff 和 range 函数，如下：

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

- codaddict

---

如果数组中有前导零，则它将无法正常工作。 - Hristian Yordanov

Answer 2

我假设这个数字是数组的元素，而不是键。我还假设这些数字从1开始，而不是0。

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

echo $Number;

- emurano

---

我喜欢这个，因为你没有使用任何函数。不错的一个。 - Jarnail S

Answer 3

对于大型排序的唯一数字数组，您可以二分搜索数组以查找未使用的最低或最高数字。成本=Log2N。例如：由于65536个项目可以在16个循环中搜索，因此...

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

所以（我不会PHP，但可以翻译...）：

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;

- user556202

Answer 4

如果给定的输入没有排序并且输入的大小非常大，则可以在任何编程语言中使用以下逻辑：

算法： 1.从大输入中将较小的块加载到内存中。 2.初始化三个变量，例如 min=0，max=0 和 missingIds=[]。 3.从左到右扫描较小的分块输入 a.如果扫描到的值在 missingIds 中，则弹出 missingIds 中的扫描值，然后继续下一个值； b.如果扫描到的值接近于 min，则查找扫描值和 min 之间的所有缺失数字，并将其推入 missingIds 中。min = 扫描值； c.否则，如果扫描到的值接近于 max，则查找扫描值和 max 之间的所有缺失数字，并将其推入 missingIds 中。max = 扫描值； 4.重复以上步骤，直到从左到右扫描完整个大输入。

PHP 示例：

<?php
$largeInput = [40,41,42,43,44,45,1,2,3,4,5,6,7,8,9,10,11,12,13,14,35,36,37,38,39,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,67,68,69,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34];
$missingIds = [];
$min = 0;
$max = 0;
$chunkSize = 10;
$chunkNo = 0;
$currentInput = array_slice($largeInput, $chunkNo, $chunkSize);
while(count($currentInput) > 0) {
    foreach($currentInput as $id) {
        if(in_array($id,$missingIds)) {
            $missingIds = array_diff($missingIds,[$id]);
            continue;
        }
        if($id <= $min) {
            $distMin = $min - $id;
            if($distMin > 2) {
                $tempArr = range($id+1,$min-1);
                $missingIds = array_merge($missingIds, $tempArr);
                $tempArr = [];
            } else if ($distMin > 1) {
                $tempArr = [$id+1];
                $missingIds = array_merge($missingIds, $tempArr);
                $tempArr = [];
            } 
            $min = $id;
        } else if ($id >= $max){
            $distMax = $id - $max;
            if($distMax > 2) {
                $tempArr = range($max+1,$id-1);
                $missingIds = array_merge($missingIds, $tempArr);
                $tempArr = [];
            } else if ($distMax > 1) {
                $tempArr = [$max+1];
                $missingIds = array_merge($missingIds, $tempArr);
                $tempArr = [];
            } 
            $max = $id;
        }   
    }
    $chunkNo++;
    $currentInput = array_slice($largeInput, $chunkNo, $chunkSize);
}
print_r($missingIds);

- Asheesh Kumar Singh

Answer 5

//$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";

返回的间隙函数可能有2个值： -1 可能表示数组已经被遍历完，没有可用的空槽或者 $k + 1 可能表示第一个可用的空槽在数组的末尾。

- David Newcomb

---

使用这个while习惯用法而不是foreach($arr as $k => $v)有特定原因吗？此外，这是否假设数组已排序，数组光标为零，并且值以1开头？而且这只提供第一个空闲插槽，这并不完全符合OP的要求。 - Tim Seguine

OP确实要求第一个空闲的插槽！计算所有值是没有意义的，因为他并不真正感兴趣。您对我的假设是正确的。您错过了我的解决方案无法找到开头或结尾的间隙这一事实！此外，示例并未说明数字将被删除或重新插入，仅说明数字将被使用。在语言中添加foreach之前，我们使用的是list/each，所以这主要只是习惯问题。这应该是给OP的教训，要写出明确产生他/她想要的结果的问题，而不要对我们做出太多假设。 - David Newcomb

它说“每个缺失的数字”; 当您发布时可能有所不同。我并不是在批评，实际上我很喜欢您的回答。 - Tim Seguine

Answer 6

也可以使用 in_array() 函数 轻松实现，如下所示：

// 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!"
     }  
}

- Nadeem Khan