php 查找数组中缺失的数字
声明:本页面是StackOverFlow热门问题的中英对照翻译,遵循CC BY-SA 4.0协议,如果您需要使用它,必须同样遵循CC BY-SA许可,注明原文地址和作者信息,同时你必须将它归于原作者(不是我):StackOverFlow
原文地址: http://stackoverflow.com/questions/4163164/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Find missing numbers in array
提问by nickifrandsen
I'm trying to find each missing number in an array like the following.
我正在尝试在如下所示的数组中找到每个缺失的数字。
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
)
The numbers 65
,66
are missing in this particular array.
数字65
,66
在此特定数组中丢失。
My question how do I figure out which numbers are missing with the help of PHP. Specifically what I need to find out is the lowest missing number.
我的问题是如何在 PHP 的帮助下找出缺少哪些数字。具体来说,我需要找出最小的缺失数字。
Why: Because then I can assign that number to a member as an id.
为什么:因为这样我就可以将该号码作为 id 分配给成员。
回答by codaddict
You can make use of array_diff
and range
functions as:
您可以使用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)
回答by emurano
I'm assuming the number is the element, not the key, of the array. I'm also assuming that the numbers start from 1, not 0.
我假设数字是数组的元素,而不是键。我还假设数字从 1 开始,而不是 0。
$Expected = 1;
foreach ($InputArray as $Key => $Number)
{
if ($Expected != $Number)
{
break;
}
$Expected++;
}
echo $Number;
回答by user556202
For big sorted arrays of unique numbers, you can binary search the array for either the lowest or highest unused number. Cost=Log2N. Example: 65536 items can be searched in 16 loops since
对于唯一数字的大排序数组,您可以二进制搜索数组以查找最低或最高的未使用数字。成本=Log2N。示例:可以在 16 次循环中搜索 65536 个项目,因为
if ( arr[hi] - arr[lo] > hi - lo )
... there are unused numbers in that range ...
So (I don't know PHP, but it can be translated...):
所以(我不懂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;
回答by Asheesh Kumar Singh
If given input is not in sorted order and size of input is very large then we can use following logic in any programming language:
如果给定的输入没有排序并且输入的大小非常大,那么我们可以在任何编程语言中使用以下逻辑:
Algorithm
算法
- bring smaller chunk into memory from large input
- initialize three variables say min = 0, max = 0 and missingIds = []
scan smaller chunked input from left to right
- if scannedValue found in missingIds then, pop scannedValue from missingIds go to next value;
If scanned value is near to min then, find all the missing numbers between scannedValue and min, push into missingIds
min = scannedValue;
Else if scanned value is near to max then, find all the missing numbers between scannedValue and max, push into missingIds
max = scannedValue;
- repeat above steps until large input scanned from left to right
- 从大输入将较小的块带入内存
- 初始化三个变量,例如 min = 0、max = 0 和 missingIds = []
从左到右扫描较小的分块输入
- 如果在 missingIds 中找到了 scanValue ,则从 missingIds 中弹出 scandValue 到下一个值;
如果扫描值接近 min,则找到 scanValue 和 min 之间的所有缺失数字,推入 missingIds
最小值 = 扫描值;
否则,如果扫描值接近最大值,则找到扫描值和最大值之间的所有缺失数字,推入 missingIds
最大值 = 扫描值;
- 重复上述步骤,直到从左到右扫描大输入
Example in PHP
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);
回答by David Newcomb
//$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";
The return of the gap function can be 2 values: -1 could indicate that the array has been traversed and there are no free slots or $k+1 which could indicate that the first free slot is on the end of the array.
gap 函数的返回值可以是 2 个值:-1 表示数组已被遍历并且没有空闲槽或 $k+1 表示第一个空闲槽位于数组的末尾。
回答by Nadeem Khan
It can also be done easily by using in_array() functionlike this:
也可以使用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!"
}
}