Проблема двух сумм, но цель находится в пределах досягаемости - PullRequest
Новая
       3

Проблема двух сумм, но цель находится в пределах досягаемости

0 голосов
/ 03 марта 2020

Я столкнулся с проблемой, аналогичной старой проблеме двух сумм, но вместо того, чтобы искать значение, оно должно находиться в пределах диапазона, и я не уверен, как эффективно подойти к нему. Вот упрощенная версия моей проблемы:

Учитывая массив целых чисел в порядке предпочтения, найдите первые два целых числа, сумма которых лежит между диапазоном X и Y st X <= sum <= Y (где X <Y и известны, то есть произвольно X = 20 и Y = 40). </p>

Я использовал метод грубой силы, используя для l oop, но я не уверены, является ли это наиболее эффективным решением. Я подумал об использовании таблицы ha sh, но я не знаю, как ее применить.

примечание: в порядке предпочтения я имею в виду возврат первых двух целых чисел, соответствующих этому критерию

Ответы [ 3 ]

0 голосов
/ 03 марта 2020

Добавьте каждый элемент к древовидной карте с ключом в качестве элемента и значением в виде списка индексов, где этот элемент встречается.

При добавлении элемента к древовидной карте проверьте, существует ли подкарта, чьи ключи варьируются от X - current_element до Y - current_element оба включительно. Если у вас есть подкарта, ваш ответ [curr_element, A[first_index_of_submap's value_of_first_key] ]

0 голосов
/ 04 марта 2020

Может быть, это метод грубой силы, который вы уже пробовали, но я думаю, что это самый простой способ.

Начиная с подмножества первых двух элементов, повторяем подмножества увеличение размера, сравнивая сумму значений каждого элемента в подмножестве и значения последнего элемента. Когда вы найдете сумму в пределах диапазона, все готово.

Это позволит найти первую пару чисел в пределах диапазона на основе определения «первым» будет «пара с наименьшим максимальным индексом». 

function findFirstSumInRange(int $min, int $max, array $values = []): array
{
    for ($b = 1, $n = count($values); $b < $n; $b++) {
        for ($a = 0; $a < $b; $a++) {
            if ($min <= ($sum = $values[$a] + $values[$b]) && $sum <= $max) {
                return [$values[$a], $values[$b]];
                // or return [$a => $values[$a], $b => $values[$b]]; if you need the keys as well
            }
        }
    }
    return [];
}

Вы можете сделать это быстрее, пропустив любые значения, которые уже превышают верхнюю границу диапазона. 

function findFirstSumInRangeB(int $min, int $max, array $values = []): array
{
    for ($b = 1, $n = count($values); $b < $n; $b++) {
        if ($values[$b] < $max) { // else these sums will all be > the range because one addend is
            for ($a = 0; $a < $b; $a++) {
                if ($values[$a] < $max && $min <= ($sum = $values[$a] + $values[$b]) && $sum <= $max) {
                    return [$a => $values[$a], $b => $values[$b]];
                }
            }
        }
    }
    return [];
}

Что касается "наиболее эффективного решения", я бы предпочитайте go для простоты, а не для оптимизации производительности, если производительность не вызывает проблем. Просто мое мнение.

0 голосов
/ 03 марта 2020

Вы можете использовать метод двоичного поиска для решения проблемы 2 сумм и настроить функцию двоичного поиска для поиска в диапазоне. Примерно так: 

$arr = [1,2,4,6,8,14,15,17];
print_r(first_sum_in_range($arr, 25, 40));



function first_sum_in_range($array, $min, $max){
    foreach ($array as $k=>$a) {
        $b = binary_search_range($array, $a, $min, $max);
        if ($b !== false) {
            return [$a,$b];
        }
    }
}

function binary_search_range($array, $a, $min, $max) {
   $top = sizeof($array) -1;
   $bot = 0;
   while($top >= $bot) 
   {
      $p = floor(($top + $bot) / 2);
      if ($a+$array[$p] < $min) $bot = $p + 1;
      elseif ($a+$array[$p] > $max) $top = $p - 1;
      else return $array[$p];
   }
   return false;
}

ВЫХОД: 

Array
(
    [0] => 8
    [1] => 17
)
...