Дано N целых чисел, подсчитать количество пар целых чисел, разница которых равна K
Мне дали массив, как это array(1,5,3,4,2);
Сказать k=2Я должен выяснить количество пар, разница которых равна 2. В этом случае он должен вернуть 3, потому что 5-3, 4-2, 3-1
Вот что я попробовал. Работает нормально, я перебираю массив дважды O(n^2) Сложность, мне интересно, есть ли лучший способ добиться этого.
$arr = array(1,5,3,4,2);
$k =2;
function find_pairs($arr, $k)
{
$count = 0;
for ($i=0 ; $i<= count($arr)-1 ; $i++)
{
for ($j=$i+1; $j <= count($arr)-1 ; $j++)
{
if ($arr[$i]-$arr[$j] == $k || $arr[$j]-$arr[$i]==$k)
{
$count++;
}
}
}
return $count;
}
echo find_pairs($arr, $k);
Спасибо
Решение
Конечно, есть много способов:
Использование сортировки:
Sort the array arr
Take two pointers, l and r, both pointing to 1st element
Take the difference arr[r] – arr[l]
If value diff is K, increment count and move both pointers to next element
if value diff > k, move l to next element
if value diff < k, move r to next element
return count
один со сложностью O (n):
1) Initialize count as 0.
2) Insert all distinct elements of arr[] in a hash map. While inserting,
ignore an element if already present in the hash map.
3) Do following for each element arr[i].
a) Look for arr[i] + k in the hash map, if found then increment count.
b) Look for arr[i] - k in the hash map, if found then increment count.
c) Remove arr[i] from hash table.
В любом случае вы можете обратиться к этому ссылка на сайт для получения дополнительной информации.
Другие решения
Да, конечно. Ниже приведено то, что вы можете использовать:
- сортировать массив (a, скажем, и n элементов)
- поиск (двоичный) для a [i] + k для всех элементов от индекса 0 до n-2. Количество успешных хитов — ваш ответ.
Это имеет сложность O (n log n).
Да уж. Вы можете использовать unordered_set. Разработка приведена ниже:
1. Insert the all elements of array into unordered_set.
2. Initialize count=0
3. for loop i=0 to i=n where n is the length of array
if arr[i]+k is found then increment count
4. Return count.
Сложность описанной выше процедуры составляет O (N).
Код php сниппет:
function find_pairs($a, $k)
{
$num = array_flip($a);
$count = 0;
foreach($num as $n => $_unused)
{
if(isset($num[$n + $k]))
{
$count++;
}
}
return $count;
}