从重复数组中寻找丢失元素的 Php 程序
假设两个数组除了一个元素之外都是重复的，也就是说其中一个数组的一个元素丢失了，我们需要找到那个丢失的元素。 例:
Input: arr1[] = {1, 4, 5, 7, 9}
arr2[] = {4, 5, 7, 9}
Output: 1
1 is missing from second array.
Input: arr1[] = {2, 3, 4, 5}
arr2[] = {2, 3, 4, 5, 6}
Output: 6
6 is missing from first array.
一个简单的解决方案是迭代数组，逐元素检查，当发现不匹配的元素时标记缺失的元素，但是这个解决方案需要数组的线性时间过大。 另一个高效解决方案是基于 一个二分搜索法的方法。算法步骤如下:
- 在更大的阵列中启动二分搜索法，获得中间 as (lo + hi) / 2
- 如果两个数组的值相同，那么缺少的元素必须在右边，因此将 lo 设置为 mid
- 否则将 hi 设置为 mid，因为如果 mid 元素不相等，丢失的元素必须在更大数组的左边。
- 一种特殊情况是单独处理的，对于单元素和零元素数组，单元素本身将是缺失的元素。 如果第一个元素本身不相等，那么该元素将是缺失的元素。/li >
以下是上述步骤的实施
服务器端编程语言（Professional Hypertext Preprocessor 的缩写）
<?php
// PHP program to find missing
// element from same arrays
// (except one missing element)
// Function to find missing
// element based on binary
// search approach. arr1[]
// is of larger size and
// N is size of it. arr1[]
// and arr2[] are assumed
// to be in same order.
function findMissingUtil($arr1, $arr2, $N)
{
// special case, for only
// element which is
// missing in second array
if ($N == 1)
return $arr1[0];
// special case, for first
// element missing
if ($arr1[0] != $arr2[0])
return $arr1[0];
// Initialize current
// corner points
$lo = 0;
$hi = $N - 1;
// loop until lo < hi
while ($lo < $hi)
{
$mid = ($lo + $hi) / 2;
// If element at mid indices are
// equal then go to right subarray
if ($arr1[$mid] == $arr2[$mid])
$lo = $mid;
else
$hi = $mid;
// if lo, hi becomes
// contiguous, break
if ($lo == $hi - 1)
break;
}
// missing element will be
// at hi index of
// bigger array
return $arr1[$hi];
}
// This function mainly
// does basic error checking
// and calls findMissingUtil
function findMissing($arr1, $arr2,
$M, $N)
{
if ($N == $M - 1)
echo "Missing Element is "
, findMissingUtil($arr1,
$arr2, $M) ;
else if ($M == $N - 1)
echo "Missing Element is "
, findMissingUtil($arr2,
$arr1, $N);
else
echo "Invalid Input";
}
// Driver Code
$arr1 = array(1, 4, 5, 7, 9);
$arr2 = array(4, 5, 7, 9);
$M = count($arr1);
$N = count($arr2);
findMissing($arr1, $arr2, $M, $N);
// This code is contributed by anuj_67.
?>
输出:
Missing Element is 1
如果输入数组不在 中，该怎么办？ 在这种情况下，缺失的元素只是两个数组所有元素的异或。感谢 Yolo Song 的建议。
服务器端编程语言（Professional Hypertext Preprocessor 的缩写）
<?php
// PHP program to find missing
// element from one array
// such that it has all elements
// of other array except
// one. Elements in two arrays
// can be in any order.
// This function mainly does
// XOR of all elements
// of arr1[] and arr2[]
function findMissing($arr1, $arr2,
$M, $N)
{
if ($M != $N - 1 && $N != $M - 1)
{
echo "Invalid Input";
return;
}
// Do XOR of all element
$res = 0;
for ($i = 0; $i < $M; $i++)
$res = $res ^ $arr1[$i];
for ($i = 0; $i < $N; $i++)
$res = $res ^ $arr2[$i];
echo "Missing element is ", $res;
}
// Driver Code
$arr1 = array(4, 1, 5, 9, 7);
$arr2 = array(7, 5, 9, 4);
$M = sizeof($arr1);
$N = sizeof($arr2);
findMissing($arr1, $arr2, $M, $N);
// This code is contributed by aj_36
?>
输出:
Missing Element is 1
更多详细信息，请参考完整文章从重复数组中查找丢失元素！
版权属于：月萌API www.moonapi.com，转载请注明出处
