Учитывая целочисленный массив и положительное целое число k, подсчитайте все различные пары с разностью, равной k.
Примеры:
Input: arr[] = {1, 5, 3, 4, 2}, k = 3
Output: 2
There are 2 pairs with difference 3, the pairs are {1, 4} and {5, 2}
Input: arr[] = {8, 12, 16, 4, 0, 20}, k = 4
Output: 5
There are 5 pairs with difference 4, the pairs are {0, 4}, {4, 8},
{8, 12}, {12, 16} and {16, 20}
Способ 1 (простой)
Простое решение состоит в том, чтобы рассмотреть все пары одну за другой и проверить разницу между каждой парой. Следующая программа реализует простое решение. Мы запускаем два цикла: внешний цикл выбирает первый элемент пары, внутренний цикл ищет другой элемент. Это решение не работает, если в массиве есть дубликаты, так как необходимо учитывать только отдельные пары.
C ++
#include<iostream>
using namespace std;
int countPairsWithDiffK(int arr[], int n, int k)
{
int count = 0;
for (int i = 0; i < n; i++)
{
for (int j = i+1; j < n; j++)
if (arr[i] - arr[j] == k || arr[j] - arr[i] == k )
count++;
}
return count;
}
int main()
{
int arr[] = {1, 5, 3, 4, 2};
int n = sizeof(arr)/sizeof(arr[0]);
int k = 3;
cout << "Count of pairs with given diff is "
<< countPairsWithDiffK(arr, n, k);
return 0;
}
|
Джава
import java.util.*;
import java.io.*;
class GFG {
static int countPairsWithDiffK(int arr[],
int n, int k)
{
int count = 0;
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
if (arr[i] - arr[j] == k ||
arr[j] - arr[i] == k)
count++;
}
return count;
}
public static void main(String args[])
{
int arr[] = { 1, 5, 3, 4, 2 };
int n = arr.length;
int k = 3;
System.out.println("Count of pairs with given diff is "
+ countPairsWithDiffK(arr, n, k));
}
}
|
python3
def countPairsWithDiffK(arr, n, k):
count = 0
for i in range(0, n):
for j in range(i+1, n) :
if arr[i] - arr[j] == k or arr[j] - arr[i] == k:
count += 1
return count
arr = [1, 5, 3, 4, 2]
n = len(arr)
k = 3
print ("Count of pairs with given diff is ",
countPairsWithDiffK(arr, n, k))
|
C #
using System;
class GFG {
static int countPairsWithDiffK(int []arr,
int n, int k)
{
int count = 0;
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
if (arr[i] - arr[j] == k ||
arr[j] - arr[i] == k)
count++;
}
return count;
}
public static void Main()
{
int []arr = { 1, 5, 3, 4, 2 };
int n = arr.Length;
int k = 3;
Console.WriteLine("Count of pairs with "
+ " given diff is "
+ countPairsWithDiffK(arr, n, k));
}
}
|
PHP
<?php
function countPairsWithDiffK($arr, $n,
$k)
{
$count = 0;
for($i = 0; $i < $n; $i++)
{
for($j = $i + 1; $j < $n; $j++)
if ($arr[$i] - $arr[$j] == $k or
$arr[$j] - $arr[$i] == $k)
$count++;
}
return $count;
}
$arr = array(1, 5, 3, 4, 2);
$n = count($arr);
$k = 3;
echo "Count of pairs with given diff is "
, countPairsWithDiffK($arr, $n, $k);
?>
|
Выход :
Count of pairs with given diff is 2
Сложность времени O (n 2 )
Способ 2 (использовать сортировку)
Мы можем найти количество за O (nLogn), используя алгоритм сортировки O (nLogn), такой как Merge Sort , Heap Sort и т. Д. Ниже приведены подробные шаги.
1) Initialize count as 0
2) Sort all numbers in increasing order.
3) Remove duplicates from array.
4) Do following for each element arr[i]
a) Binary Search for arr[i] + k in subarray from i+1 to n-1.
b) If arr[i] + k found, increment count.
5) Return count.
C ++
#include <iostream>
#include <algorithm>
using namespace std;
int binarySearch(int arr[], int low, int high, int x)
{
if (high >= low)
{
int mid = low + (high - low)/2;
if (x == arr[mid])
return mid;
if (x > arr[mid])
return binarySearch(arr, (mid + 1), high, x);
else
return binarySearch(arr, low, (mid -1), x);
}
return -1;
}
int countPairsWithDiffK(int arr[], int n, int k)
{
int count = 0, i;
sort(arr, arr+n);
for (i = 0; i < n-1; i++)
if (binarySearch(arr, i+1, n-1, arr[i] + k) != -1)
count++;
return count;
}
int main()
{
int arr[] = {1, 5, 3, 4, 2};
int n = sizeof(arr)/sizeof(arr[0]);
int k = 3;
cout << "Count of pairs with given diff is "
<< countPairsWithDiffK(arr, n, k);
return 0;
}
|
Джава
import java.util.*;
import java.io.*;
class GFG {
static int binarySearch(int arr[], int low,
int high, int x)
{
if (high >= low)
{
int mid = low + (high - low) / 2;
if (x == arr[mid])
return mid;
if (x > arr[mid])
return binarySearch(arr, (mid + 1),
high, x);
else
return binarySearch(arr, low,
(mid - 1), x);
}
return -1;
}
static int countPairsWithDiffK(int arr[], int n, int k)
{
int count = 0, i;
Arrays.sort(arr);
for (i = 0; i < n - 1; i++)
if (binarySearch(arr, i + 1, n - 1,
arr[i] + k) != -1)
count++;
return count;
}
public static void main(String args[])
{
int arr[] = { 1, 5, 3, 4, 2 };
int n = arr.length;
int k = 3;
System.out.println("Count of pairs with given diff is "
+ countPairsWithDiffK(arr, n, k));
}
}
|
питон
def binarySearch(arr, low, high, x):
if (high >= low):
mid = low + (high - low)//2
if x == arr[mid]:
return (mid)
elif(x > arr[mid]):
return binarySearch(arr, (mid + 1), high, x)
else:
return binarySearch(arr, low, (mid -1), x)
return -1
def countPairsWithDiffK(arr, n, k):
count = 0
arr.sort()
for i in range (0, n - 2):
if (binarySearch(arr, i + 1, n - 1,
arr[i] + k) != -1):
count += 1
return count
arr= [1, 5, 3, 4, 2]
n = len(arr)
k = 3
print ("Count of pairs with given diff is ",
countPairsWithDiffK(arr, n, k))
|
C #
using System;
class GFG {
static int binarySearch(int []arr, int low,
int high, int x)
{
if (high >= low)
{
int mid = low + (high - low) / 2;
if (x == arr[mid])
return mid;
if (x > arr[mid])
return binarySearch(arr, (mid + 1),
high, x);
else
return binarySearch(arr, low,
(mid - 1), x);
}
return -1;
}
static int countPairsWithDiffK(int []arr,
int n, int k)
{
int count = 0, i;
Array.Sort(arr);
for (i = 0; i < n - 1; i++)
if (binarySearch(arr, i + 1, n - 1,
arr[i] + k) != -1)
count++;
return count;
}
public static void Main()
{
int []arr = { 1, 5, 3, 4, 2 };
int n = arr.Length;
int k = 3;
Console.WriteLine("Count of pairs with"
+ " given diff is "
+ countPairsWithDiffK(arr, n, k));
}
}
|
PHP
<?php
function binarySearch($arr, $low,
$high, $x)
{
if ($high >= $low)
{
$mid = $low + ($high - $low)/2;
if ($x == $arr[$mid])
return $mid;
if ($x > $arr[$mid])
return binarySearch($arr, ($mid + 1),
$high, $x);
else
return binarySearch($arr, $low,
($mid -1), $x);
}
return -1;
}
function countPairsWithDiffK($arr, $n, $k)
{
$count = 0;
$i;
sort($arr);
for ($i = 0; $i < $n - 1; $i++)
if (binarySearch($arr, $i + 1, $n - 1,
$arr[$i] + $k) != -1)
$count++;
return $count;
}
$arr = array(1, 5, 3, 4, 2);
$n = count($arr);
$k = 3;
echo "Count of pairs with given diff is "
, countPairsWithDiffK($arr, $n, $k);
?>
|
Выход:
Count of pairs with given diff is 2
Сложность времени: первый шаг (сортировка) занимает время O (nLogn). Второй шаг запускает двоичный поиск n раз, поэтому временная сложность второго шага также равна O (nLogn). Следовательно, общая временная сложность составляет O (nLogn). Второй шаг можно оптимизировать до O (n), смотрите это .
Способ 3 (использовать самобалансирующийся BST)
Мы также можем использовать самобалансирующийся BST, такой как дерево AVL или дерево Red Black, чтобы решить эту проблему. Ниже приводится подробный алгоритм.
1) Initialize count as 0.
2) Insert all elements of arr[] in an AVL tree. While inserting,
ignore an element if already present in AVL tree.
3) Do following for each element arr[i].
a) Search for arr[i] + k in AVL tree, if found then increment count.
b) Search for arr[i] - k in AVL tree, if found then increment count.
c) Remove arr[i] from AVL tree.
Временная сложность вышеупомянутого решения также равна O (nLogn), поскольку операции поиска и удаления занимают O (Logn) время для самобалансирующегося бинарного дерева поиска.
Метод 4 (использовать хеширование)
Мы также можем использовать хеширование для достижения средней сложности времени как 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.
Очень простой случай, когда хеширование работает за время O (n), — это случай, когда диапазон значений очень мал. Например, в следующей реализации диапазон чисел предполагается равным от 0 до 99999. Можно использовать простую технику хеширования для использования значений в качестве индекса.
#define MAX 100000
int countPairsWithDiffK(int arr[], int n, int k)
{
int count = 0;
bool hashmap[MAX] = {false};
for (int i = 0; i < n; i++)
hashmap[arr[i]] = true;
for (int i = 0; i < n; i++)
{
int x = arr[i];
if (x - k >= 0 && hashmap[x - k])
count++;
if (x + k < MAX && hashmap[x + k])
count++;
hashmap[x] = false;
}
return count;
}
|
Метод 5 (использовать сортировку)
- Сортировать массив обр
- Возьмите два указателя, l и r, оба указывают на 1-й элемент
- Возьмите разницу arr [r] — arr [l]
- Если значение diff равно K, увеличить счетчик и переместить оба указателя на следующий элемент
- если значение diff> k, переместить l к следующему элементу
- если значение diff <k, перейти к следующему элементу
- счетчик возвратов
C ++
#include <iostream>
#include <algorithm>
using namespace std;
int countPairsWithDiffK(int arr[], int n, int k)
{
int count = 0;
sort(arr, arr+n);
int l = 0;
int r = 0;
while(r < n)
{
if(arr[r] - arr[l] == k)
{
count++;
l++;
r++;
}
else if(arr[r] - arr[l] > k)
l++;
else
r++;
}
return count;
}
int main()
{
int arr[] = {1, 5, 3, 4, 2};
int n = sizeof(arr)/sizeof(arr[0]);
int k = 3;
cout << "Count of pairs with given diff is "
<< countPairsWithDiffK(arr, n, k);
return 0;
}
|
Джава
import java.util.*;
class GFG {
static int countPairsWithDiffK(int arr[], int n,
int k)
{
int count = 0;
Arrays.sort(arr);
int l = 0;
int r = 0;
while(r < n)
{
if(arr[r] - arr[l] == k)
{
count++;
l++;
r++;
}
else if(arr[r] - arr[l] > k)
l++;
else
r++;
}
return count;
}
public static void main(String[] args)
{
int arr[] = {1, 5, 3, 4, 2};
int n = arr.length;
int k = 3;
System.out.println("Count of pairs with given diff is " +
countPairsWithDiffK(arr, n, k));
}
}
|
python3
def countPairsWithDiffK(arr,n,k):
count =0
arr.sort()
l =0
r=0
while r<n:
if arr[r]-arr[l]==k:
count+=1
l+=1
r+=1
elif arr[r]-arr[l]>k:
l+=1
else:
r+=1
return count
if __name__=='__main__':
arr = [1, 5, 3, 4, 2]
n = len(arr)
k = 3
print("Count of pairs with given diff is ",
countPairsWithDiffK(arr, n, k))
|
C #
using System;
class GFG {
static int countPairsWithDiffK(int []arr,
int n, int k)
{
int count = 0;
Array.Sort(arr);
int l = 0;
int r = 0;
while(r < n)
{
if(arr[r] - arr[l] == k)
{
count++;
l++;
r++;
}
else if(arr[r] - arr[l] > k)
l++;
else
r++;
}
return count;
}
public static void Main()
{
int []arr = {1, 5, 3, 4, 2};
int n = arr.Length;
int k = 3;
Console.Write("Count of pairs with "
+ "given diff is " +
countPairsWithDiffK(arr, n, k));
}
}
|
PHP
<?php
function countPairsWithDiffK( $arr, $n, $k)
{
$count = 0;
sort($arr);
$l = 0;
$r = 0;
while($r < $n)
{
if($arr[$r] - $arr[$l] == $k)
{
$count++;
$l++;
$r++;
}
else if($arr[$r] - $arr[$l] > $k)
$l++;
else
$r++;
}
return $count;
}
$arr = array(1, 5, 3, 4, 2);
$n =count($arr);
$k = 3;
echo "Count of pairs with given diff is "
, countPairsWithDiffK($arr, $n, $k);
?>
|
Выход:
Count of pairs with given diff is 2
Сложность времени: O (nlogn)
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме
Рекомендуемые посты:
- Подсчитайте пары в массиве так, чтобы разница между ними и их индексами была равна
- Количество пар между двумя массивами, так что суммы различны
- Подсчитайте разные пары из двух массивов, имеющих одинаковую сумму цифр
- Подсчет пар, образованных отдельными подмассивами элементов
- Подсчитать количество различных пар, сумма которых существует в данном массиве
- Подсчет пар с установленной суммой битов, равной K
- Подсчет равных пар из заданных строковых массивов
- Подсчет равных пар элементов в данном массиве
- Подсчет пар из двух связанных списков, сумма которых равна заданному значению
- Подсчет пар из двух отсортированных массивов, сумма которых равна заданному значению x
- Количество индексных пар с равными элементами в массиве
- Подсчитайте пары в массиве так, чтобы оба элемента имели равные установленные биты
- Подсчитайте пары в массиве так, чтобы абсолютная разница между ними составляла ≥ K
- Подсчет пар символов в строке, разница значений ASCII которой равна K
- Самый длинный подмассив с разницей в 1 и 0 равен k
Подсчитайте все разные пары с разностью, равной k
0.00 (0%) 0 votes