Nombre de paires avec une différence d’au plus K sans répétition d’élément

Étant donné un tableau arr[] et un nombre Kla tâche consiste à compter le nombre de paires dont la différence est inférieure ou égale au K, de sorte qu’un élément ne peut être considéré que dans une seule paire.

Exemples:

Saisir: arr[] = {1, 3, 3, 9, 4}, K = 2
Production: 2
Explication:
Il n’y a que deux paires dont la différence est d’au plus 2
(1, 3), (3, 4)

Saisir: arr[] = {1, 4, 3, 7, 5}, K = 2
Production: 2
Explication:
Il y a cinq paires dans le tableau dont la différence est d’au plus 2,
(1, 3), (3, 4), (4, 5), (3, 5), (5, 7)
Mais seuls deux d’entre eux peuvent être considérés à la fois car un élément
ne peut être pris par paire qu’une seule fois.

Untitled Diagram621

Approcher:
L’idée est de trier le tableau et trouver le différence des éléments adjacentsSi la différence est au plus K, alors la paire est considérée et le compte est augmenté puis, selon la condition, tout élément ne peut être que dans une seule paire, puis si une paire est trouvée, le compteur incrémente de 2 tels que tout élément est présent dans une seule paire.

Par exemple:

Given Array - {1, 4, 3, 7, 5}, K = 2 
After Sorting Array will be - {1, 3, 4, 5, 7}
Step 1 - i = 0, count = 0
Consider the pair of elements for i and i + 1
Pair - (1, 3), Difference = 3 - 1 = 2
As the Difference is less than equal to 2
count = 1 and i = 2

Step 2 - i = 2, count = 1
Consider the pair of elements for i and i + 1
Pair - (4, 5), Difference = 5 - 4 = 1
As the Difference is less than equal to 2
count = 2 and i = 4
As i is greater than length-2,
there will be no more possible pairs.

Algorithme:

  • Trier le tableau en utilisant n’importe quel algorithme de tri tels que les éléments consécutifs sont ensemble.
  • Initialiser le compteur d’index (disons je) à zéro et exécutez un boucle while jusqu’à ce que le compteur d’index soit inférieur à (longueur – 1)
    1. Vérifiez la différence des éléments à l’index je et je + 1.
    2. Si la différence est inférieure ou égale à K, incrémentez l’indice de 2 et incrémentez également le compteur de 1 pour considérer l’augmentation, les éléments augmentent d’un coup.
    3. Sinon, incrémentez l’indice de 1 pour considérer la paire formée par l’élément suivant.

Voici la mise en œuvre de l’approche ci-dessus :

C++

#include <iostream>

#include<bits/stdc++.h>

using namespace std;

    

    

    

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

    {

        

        

        

        int pair = 0;

        int index = 0;

        

        

        

        

        sort(arr,arr + n) ;

                

        

        

        while(index < n -1)

        {

            

            

            

            if (arr[index + 1] - arr[index] <= k){

                pair += 1 ;

                index += 2 ;

            }

            else{

                index += 1;

            }

        }

        return pair ;

    

    }

    

int main() {

    int arr[] = {1, 4, 3, 7, 5} ;

    int k = 2;

    

     int n = sizeof(arr)/sizeof(arr[0]);

    

    int count = countPairs(arr, k,n) ;

    cout << count << endl;;

}

Java

import java.util.*;

class GFG

{

    

    

    

    static int countPairs(int arr[], int k)

    {

        

        

        Arrays.sort(arr) ;

        

        

        

        int pair = 0;

        int index = 0;

        

        

        

        while(index < arr.length -1)

        {

            

            

            

            if (arr[index + 1] - arr[index] <= k){

                pair += 1 ;

                index += 2 ;

            }

            else{

                index += 1;

            }

        }

        return pair ;

    

    }

    

    

    public static void main (String[] args) {

        int arr[] = {1, 4, 3, 7, 5} ;

        int k = 2;

        

        

        int count = countPairs(arr, k) ;

        System.out.println(count);

    }

}

Python3

def countPairs(arr, k):

    

    

    arr.sort()

    

    

    

    pair = 0

    index = 0

    

    

    

    while(index < len(arr)-1):

        

        

        

        if arr[index + 1] - arr[index] <= k:

            pair += 1

            index += 2

        else:

            index += 1

            

    return pair

if __name__ == "__main__":

    arr = [1, 4, 3, 7, 5]

    k = 2

    

    count = countPairs(arr, k)

    print(count)

C#

using System;

class GFG

{

    

    

    

    static int countPairs(int []arr, int k)

    {

        

        

        Array.Sort(arr) ;

        

        

        

        int pair = 0;

        int index = 0;

        

        

        

        while(index < arr.Length - 1)

        {

            

            

            

            if (arr[index + 1] - arr[index] <= k)

            {

                pair += 1 ;

                index += 2 ;

            }

            else

            {

                index += 1;

            }

        }

        return pair ;

    }

    

    

    public static void Main ()

    {

        int []arr = {1, 4, 3, 7, 5} ;

        int k = 2;

        

        

        int count = countPairs(arr, k) ;

        Console.WriteLine(count);

    }

}

Javascript

<script>

    

    

    

    

    

    

    function countPairs(arr, k, n)

    {

        

        

        

        let pair = 0;

        let index = 0;

        

        

        

        

        arr.sort((a, b) => a - b) ;

                

        

        

        while(index < n -1)

        {

            

            

            

            if (arr[index + 1] - arr[index] <= k){

                pair += 1 ;

                index += 2 ;

            }

            else{

                index += 1;

            }

        }

        return pair ;

    

    }

    

let arr = [1, 4, 3, 7, 5];

let k = 2;

    

let n = arr.length;

let count = countPairs(arr, k,n);

document.write(count + "<br>");

</script>

Analyse de performance:

  • Complexité temporelle : Dans l'approche ci-dessus, il y a un tri du tableau qui prend O(N logN), et il y a aussi une itération pour compter le nombre de paires qui est O(N).
    Par conséquent, la complexité globale de l'approche est O(N logN + N).
  • Complexité spatiale : Dans l'approche ci-dessus, il n'y a pas d'espace supplémentaire. Par conséquent, la complexité spatiale globale de l'approche sera O(1)

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Aller en haut