Рубрики

Подсчитайте все разные пары с разностью, равной k

Учитывая целочисленный массив и положительное целое число 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 ++

/ * Простая программа для подсчета пар с разницей k * /
#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;

}

Джава

// Простая Java-программа для
// считать пары с разницей k

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));

    }

}

  
// Этот код добавлен
// от Sahil_Bansall

python3

# Простая программа для подсчета пар с разницей k

  

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 #

// Простая программа на 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));

    }

}

  
// Этот код предоставлен Sam007.

PHP

<?php
// Простая PHP-программа для подсчета
// пары с разностью k

  

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);

          
// Этот код предоставлен anuj_67.
?>


Выход :

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 ++

/ * Программа на основе сортировки для подсчета пар с разницей k * /
#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;

}

  
/ * Возвращает количество пар с разницей k в arr [] размера n. * /

int countPairsWithDiffK(int arr[], int n, int k)

{

    int count = 0, i;

    sort(arr, arr+n);  // Сортировка элементов массива

  

    / * код для удаления дубликатов из arr [] * /

    

    // Выбрать первую точку элемента

    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;

}

Джава

// Сортировка базовой Java-программы для
// считать пары с разницей k

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;

    }

  

    // Возвращает количество пар с

    // разница k в arr [] размера n.

    static int countPairsWithDiffK(int arr[], int n, int k)

    {

        int count = 0, i;

          

        // Сортировка элементов массива

        Arrays.sort(arr);

  

        // код для удаления дубликатов из 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));

    }

}

  
// Этот код предоставлен Sahil_Bansall

питон

# Программа на основе сортировки для
Количество пар с разницей 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

  

  
# Возвращает количество пар с
# разница k в arr [] размера n.

def countPairsWithDiffK(arr, n, k):

  

    count = 0

    arr.sort() # Сортировать элементы массива

  

    # код для удаления

    # дубликаты из arr []

  

    # Выберите первую точку элемента

    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)) 

  
# Этот код добавлен
# by Shivi_Aggarwal

C #

// Сортировка базовой программы на C # для
// считать пары с разницей k

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;

    }

  

    // Возвращает количество пар с

    // разница k в arr [] размера n.

    static int countPairsWithDiffK(int []arr, 

                                   int n, int k)

    {

          

        int count = 0, i;

          

        // Сортировка элементов массива

        Array.Sort(arr);

  

        // код для удаления дубликатов из 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));

    }

}

  
// Этот код предоставлен Sam007.

PHP

<?php
// Программа на основе сортировки PHP для
// считать пары с разницей k

  
// Стандартная функция двоичного поиска

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;

}

  
/ * Возвращает количество пар с

   разница k в arr [] размера n. * /

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);

           
// Этот код предоставлен anuj-67.
?>


Выход:

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. Можно использовать простую технику хеширования для использования значений в качестве индекса.

/ * Эффективная программа для подсчета пар с разницей k, когда диапазон

   цифры маленькие * /

#define MAX 100000

int countPairsWithDiffK(int arr[], int n, int k)

{

    int count = 0;  // Инициализировать счет

  

    // Инициализировать пустой хэш-карту.

    bool hashmap[MAX] = {false};

  

    // Вставить элементы массива в hashmap

    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 ++

/ * Программа на основе сортировки для подсчета пар с разницей k * /
#include <iostream>
#include <algorithm>

using namespace std;

   
/ * Возвращает количество пар с разницей k в arr [] размера n. * /

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 // arr [r] - arr [l] <сумма

              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;

}

Джава

// Программа сортировки на Java
// считать пары с разницей k

import java.util.*;

  

class GFG {

  
/ * Возвращает количество пар с
разница k в arr [] размера n. * /

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 // arr [r] - arr [l] <сумма

            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));

}
}

  
// Этот код предоставлен Prerna Saini

python3

# Программа на основе сортировки для
Количество пар с разницей k

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

              

        # arr [r] - arr [l] <сумма

        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))

  
# Этот код предоставлен
# Shrikant13

C #

// Программа C # на основе сортировки для подсчета
// пары с разностью k

using System;

  

class GFG {

  

    / * Возвращает количество пар с

    разница k в arr [] размера n. * /

    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 // arr [r] - arr [l] <сумма

                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
// Программа на основе сортировки для подсчета
// пары с разностью k

  
// Возвращает количество пар с
// разница k в arr [] размера n.

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++;

              

        // arr [r] - arr [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);

          
// Этот код предоставлен anuj_67,
?>

Выход:

Count of pairs with given diff is 2

Сложность времени: O (nlogn)

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Подсчитайте все разные пары с разностью, равной k

0.00 (0%) 0 votes