Логика пересечения кажется мне неправильной, поскольку мы должны проверить, существует ли отношение, образованное [a , b], например, [1,2], в $outArr или нет.Текущая проверка count(array_intersect($outArr[$k], $a)) > 1 не заботится об этом.Он скорее проверяет, присутствует ли какой-либо элемент в $outArr[$k] в $a или нет.
Итак, измените текущую логику с:
/* find the enemeies */
$intersects = array();
for($k = 0; $k < count($outArr); $k++){
if (count(array_intersect($outArr[$k], $a)) > 1 || count(array_intersect($outArr[$k], $b)) > 1) {
$intersects[] = $outArr[$k];
}
}
/* remove first and last items which are basically equal to $a and $b */
$intersects = array_slice($intersects, 1, -1);
на
$intersects = array();
foreach($a as $index => $val1){
$val2 = $b[$index];
foreach($outArr as $current_group){
if(in_array($val1,$current_group) && in_array($val2,$current_group)){ // check if both exist as they are enemies
$intersects[] = $current_group;
}
}
}
Демонстрация: https://3v4l.org/Q2rnP
В приведенном выше коде мы:
перебираем все элементы $a и одновременно с $b с помощью $index в foreach.
Проверьте, подходит ли текущая группа в $outArr, как $a[$index] (он же $val1), так и $b[$index](иначе $val2) существуют в группе или нет.
Если оба существуют в текущей группе, мы помещаем их в пересечение, поскольку они являются врагами.Ваша остальная логика правильна.
Эффективное решение:
- Мы должны использовать эту строку:
Группа определяется как интервал (x, y), так что все собаки в диапазоне от x до y образуют группу.
Это означает, что нам нужно смотреть на подмассивы (как вы правильно поняли) вместо подпоследовательностей.
Теперь мы делаем цикл от 1 до N, и если мы найдем число, у которого есть враг слева, мы можем сформировать только следующие группы из этого числа + 1и далее.Все, что перед ними, не может быть включено, так как мы смотрим на подмассивы.
Например, давайте предположим, что 5 - враг 3 в линии 1до 5 и других врагов нет.Итак, групповые формирования будут выглядеть следующим образом.
Представление:
1 2 3 4 5
-1 -1 5 -1 3
|___|
|___|___|
|___|___|___|
|___|
|___|___|
|___|
|___| // the connection/group (4,5) remains and breaks everything before 4 since 3 is an enemy of 5 and we are looking for subarrays. So everything before 4 is disconnected anyway.
Итак, наше следующее начальное животное/ собака, с которой нужно смотреть: 4.
Для каждого врага / животного мы поддерживаем ближайшего врага слева, если он присутствует.Если есть, мы обновляем следующее животное, чтобы искать группы, как доказано выше.В приведенном ниже коде $prev_start - это переменная, которая поддерживает следующее животное для просмотра.
Чтобы получить ближайшего врага слева для каждого животного, мы предварительно обрабатываем детали противника следующим образом:
Предварительная обработка:
$enemies = array_combine(range(1,$n),array_fill(0,$n,-1)); // nothing tricky, just generates an array filled with sequential numbers as keys and sets it's value as -1
foreach($a as $index => $enemy_1){
$enemy_2 = $b[$index];
if($enemy_1 < $enemy_2){
$enemies[$enemy_2] = max($enemies[$enemy_2],$enemy_1);
}else if($enemy_2 < $enemy_1){
$enemies[$enemy_1] = max($enemies[$enemy_1],$enemy_2);
}
}
Вычисления:
$prev_start = 1;
$count = 0;
for($i=1;$i<=$n;++$i){
if($enemies[$i] !== -1){
$prev_start = max($enemies[$i] + 1,$prev_start);
}
$count += ($i - $prev_start + 1);
}
Поскольку мы предварительно обработали детали противника, мы обновляем $prev_start соответственно с того места, где мынеобходимо снова начать подсчет групп.
$count += ($i - $prev_start + 1); просто подсчитывает количество групп (подмассивов), которые необходимо учитывать при подсчете.
Сложность времени: O(m + n), где m - количество пар, а n - количество собак / животных.
- Сложность пространства:
O(n), где n - количество собак / животных.
Полный код:
<?php
function countSubarrays($n, $a, $b) {
$enemies = array_combine(range(1,$n),array_fill(0,$n,-1)); // nothing tricky, just generates an array filled with sequential numbers as keys and sets it's value as -1
foreach($a as $index => $enemy_1){
$enemy_2 = $b[$index];
if($enemy_1 < $enemy_2){
$enemies[$enemy_2] = max($enemies[$enemy_2],$enemy_1);
}else if($enemy_2 < $enemy_1){
$enemies[$enemy_1] = max($enemies[$enemy_1],$enemy_2);
}
}
$prev_start = 1;
$count = 0;
for($i=1;$i<=$n;++$i){
if($enemies[$i] !== -1){
$prev_start = max($enemies[$i] + 1,$prev_start);
}
$count += ($i - $prev_start + 1);
}
return $count;
}
Демо: https://3v4l.org/1W26C