Алго-решение
Есть способ проверить, нет ли пропущенного числа, используя алгоритм. Это объясняется здесь. Обычно, если нам нужно складывать числа от 1 до 100. Нам не нужно вычислять, суммируя их, нам просто нужно сделать следующее: (100 * (100 + 1)) / 2
. Итак, как это решит нашу проблему?
Мы собираемся получить первый элемент массива и последний. Рассчитываем сумму с помощью этого алгоритма. Затем мы используем array_sum()
для вычисления фактической суммы. Если результаты совпадают, значит, пропущенного числа нет. Затем мы могли бы отследить недостающее число, вычтя фактическую сумму из рассчитанной. Это, конечно, работает только в том случае, если отсутствует только один номер, и не удастся, если пропущено несколько. Итак, давайте поместим это в код:
$range = range(0,7); // Creating an array
echo check($range) . "\r\n"; // check
unset($range[3]); // unset offset 3
echo check($range); // check
function check($array){
if($array[0] == 0){
unset($array[0]); // get ride of the zero
}
sort($array); // sorting
$first = reset($array); // get the first value
$last = end($array); // get the last value
$sum = ($last * ($first + $last)) / 2; // the algo
$actual_sum = array_sum($array); // the actual sum
if($sum == $actual_sum){
return $last + 1; // no missing number
}else{
return $sum - $actual_sum; // missing number
}
}
Вывод
8
3
Интернет-демонстрация
Если пропущено несколько номеров, просто используйте array_map()
или что-то подобное, чтобы создать внутренний цикл.
Решение с регулярным выражением
Давайте перейдем на новый уровень и воспользуемся регулярным выражением! Я знаю, что это ерунда, и ее не следует использовать в реальных приложениях. Цель - показать истинную мощь регулярного выражения :)
Итак, сначала давайте сделаем строку из нашего диапазона в следующем формате: I,II,III,IIII
для диапазона 1,3
.
$range = range(0,7);
if($range[0] === 0){ // get ride of 0
unset($range[0]);
}
$str = implode(',', array_map(function($val){return str_repeat('I', $val);}, $range));
echo $str;
вывод должен выглядеть примерно так: I,II,III,IIII,IIIII,IIIIII,IIIIIII
.
Я придумал следующее регулярное выражение: ^(?=(I+))(^\1|,\2I|\2I)+$
. Так что это значит?
^ # match begin of string
(?= # positive lookahead, we use this to not "eat" the match
(I+) # match I one or more times and put it in group 1
) # end of lookahead
( # start matching group 2
^\1 # match begin of string followed by what's matched in group 1
| # or
,\2I # match a comma, with what's matched in group 2 (recursive !) and an I
| # or
\2I # match what's matched in group 2 and an I
)+ # repeat one or more times
$ # match end of line
Посмотрим, что на самом деле происходит ....
I,II,III,IIII,IIIII,IIIIII,IIIIIII
^
(I+) do not eat but match I and put it in group 1
I,II,III,IIII,IIIII,IIIIII,IIIIIII
^
^\1 match what was matched in group 1, which means I gets matched
I,II,III,IIII,IIIII,IIIIII,IIIIIII
^^^ ,\2I match what was matched in group 1 (one I in thise case) and add an I to it
I,II,III,IIII,IIIII,IIIIII,IIIIIII
^^^^ \2I match what was matched previously in group 2 (,II in this case) and add an I to it
I,II,III,IIII,IIIII,IIIIII,IIIIIII
^^^^^ \2I match what was matched previously in group 2 (,III in this case) and add an I to it
We're moving forward since there is a + sign which means match one or more times,
this is actually a recursive regex.
We put the $ to make sure it's the end of string
If the number of I's don't correspond, then the regex will fail.
Посмотрите, как он работает и не работает. И давайте поместим это в код PHP:
$range = range(0,7);
if($range[0] === 0){
unset($range[0]);
}
$str = implode(',', array_map(function($val){return str_repeat('I', $val);}, $range));
if(preg_match('#^(?=(I*))(^\1|,\2I|\2I)+$#', $str)){
echo 'works !';
}else{
echo 'fails !';
}
Теперь давайте учтем, чтобы вернуть пропущенное число, мы удалим конечный символ $
, чтобы наше регулярное выражение не сработало, и мы используем группу 2 для возврата пропущенного числа:
$range = range(0,7);
if($range[0] === 0){
unset($range[0]);
}
unset($range[2]); // remove 2
$str = implode(',', array_map(function($val){return str_repeat('I', $val);}, $range));
preg_match('#^(?=(I*))(^\1|,\2I|\2I)+#', $str, $m); // REGEEEEEX !!!
$n = strlen($m[2]); //get the length ie the number
$sum = array_sum($range); // array sum
if($n == $sum){
echo $n + 1; // no missing number
}else{
echo $n - 1; // missing number
}
Интернет-демонстрация
person
HamZa
schedule
15.08.2013
$range = [0,1,2,3,4,6,7];
вместо:$range = array(0,1,2,3,4,6,7);
- возможно, есть и другие проблемы - остальное я не проверял. - person Nir Alfasi   schedule 16.08.2013[0, 1, 2, 2, 3]
? Это действительно так? - person Ja͢ck   schedule 19.08.2013$range
- это, по сути, набор ключей, которые находятся в уникальном индексе, поэтому повторения не должны происходить (на языке RFC 2119). - person Ben Harold   schedule 23.08.2013