Недавно мне пришлось выполнить вызов кода, где мне было поручено, чтобы для набора чисел находилось число пар, чья разница была K. Например, учитывая номера 1, 5, 3, 4, 2 и разность K ( 2) имеется 3 пары: (5,3) (4,2) (3,1). Я пробовал этот вызов в PHP. Мой код прошел тест, но был неэффективен, я думаю, потому что часть теста была отсрочена. Может ли кто-нибудь сказать мне, как я мог бы улучшить его? Я избиваю голову, потому что не могу понять, как я могу сделать ее более эффективной.
Вот мой код
<?php // Open STDIN for reading $stdin = fopen('php://stdin', 'r'); // Get the input while(!feof($stdin)) { $inputs[] = explode(' ', fgets($stdin)); } fclose($handle); $k = $inputs[0][1]; $values = array_map('intval', array_values($inputs[1])); // Sort in decending order rsort($values); // Given the difference, K, find a pair for $left within // $right whose difference is K function findPair($k, $left, $right){ foreach($right as $n) { if($left - $n == $k) return $n; // If the difference is greater than $k, there is no pair if($left - $n > $k) return false; } return false; } $pairs = 0; while(count($values) > 1){ $left = array_shift($values); $n = findPair($k, $left, $values); if($n !== false) $pairs++; } echo $pairs; ?>
Ваш код имеет сложность O(n^2) – и поэтому он будет неэффективен для больших наборов данных. Это O(n^2) поскольку вы перебираете весь массив с помощью foreach внутри вашей функции и вызываете ее while внешнем цикле.
Но вы можете легко сделать материал с помощью O(nx log(N)) :
function binSearch($array, $value, $from=null, $till=null) { $from = isset($from)?$from:0; $till = isset($till)?$till:count($array)-1; if($till<$from) { return null; } $middle = (int)($from + ($till - $from)/2); if($array[$middle]>$value) { return binSearch($array, $value, $from, $middle-1); } if($array[$middle]<$value) { return binSearch($array, $value, $middle+1, $till); } return $middle; } $data = [1, 5, 3, 4, 2]; $k = 2; sort($data); //O(nx log(n)) $count = 0; foreach($data as $value) //O(n) { $count += null===binSearch($data, $value+$k)?0:1;//O(log(N)) } var_dump($count);
-so, вы будете использовать стандартную sort() с сложностью O(n log(n)) а затем используйте двоичный поиск N раз. Бинарный поиск имеет O(log(n)) complexity , поэтому сложность цикла будет также O(n log (n)) . Таким образом, сложность всего кода будет равна O(n log(n)) + O(n log(n)) = O(n log(n)) .
Примечание: стандартная PHP- in_array() имеет сложность O(N) , поэтому ее использование даст оценку сложности O(N^2) для цикла и, следовательно, сложность кода O(N^2) .
Примечание. Сортировка через sort() приведет к быстрой сортировке . Этот алгоритм имеет среднюю сложность O(n log(n)) , в худшем случае O(N^2) – поэтому могут быть случаи наборов данных, для которых вышеприведенный код также может быть неэффективным. Вы можете изучить другие алгоритмы сортировки . Например, если ваша проблема ограничена по времени, вы можете попробовать сортировать слияние – это будет очень быстро (но это займет дополнительное пространство).
Примечание . Если говорить о временной сложности и сложности пространства, это не имеет значения, это просто простая хэш-карта, которая может быть использована. В PHP это просто массив:
$array = [1, 5, 3, 4, 2]; $k = 2; $count = 0; $map = []; foreach ($array as $number) //O(n) time { $map[$number] = $number; } foreach($map as $key=>$nevermind) //O(n) time { //O(1) if there are no duplicates, very close to O(1) otherwise $count += array_key_exists($key+$k, $map); } var_dump($count);
– это приведет к сложности времени O(2n)=O(n) сложности пространства O(2n)=O(n) .