Recuento de todos los pares en una array con diferencia absoluta mínima

Dada una array de enteros arr[] de tamaño N , la tarea es contar el número total de pares distintos que tienen una diferencia absoluta mínima. 
Ejemplos: 
 

Entrada: arr[] = {4, 2, 1, 3} 
Salida: 3 
Explicación: 
La diferencia absoluta mínima entre los pares {1, 2}, {2, 3}, {3, 4} es 1.
Entrada: arr [] = {1, 3, 8, 10, 15} 
Salida: 2 
Explicación: 
La diferencia absoluta mínima entre los pares {1, 3}, {8, 10} es 2. 
 

Enfoque: La idea es contar la frecuencia de la diferencia absoluta mínima de los elementos adyacentes de los elementos ordenados de la array dada. Siga los pasos a continuación para resolver el problema: 
 

1. Ordena la array dada arr[] .
2. Compare todos los pares adyacentes en la array ordenada y encuentre la diferencia absoluta mínima entre todos los pares adyacentes.
3. Finalmente, cuente todos los pares adyacentes que tengan una diferencia igual a la diferencia mínima.

A continuación se muestra la implementación del enfoque anterior:
 

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count of all
// pairs having minimal absolute difference
int numberofpairs(int arr[], int N)
{
    // Stores the count of pairs
    int answer = 0;
 
    // Sort the array
    sort(arr, arr + N);
 
    // Stores the minimum difference
    // between adjacent pairs
    int minDiff = INT_MAX;
    for (int i = 0; i < N - 1; i++)
 
        // Update the minimum
        // difference between pairs
        minDiff = min(minDiff,
                      arr[i + 1] - arr[i]);
 
    for (int i = 0; i < N - 1; i++) {
 
        if (arr[i + 1] - arr[i] == minDiff)
 
            // Increase count of
            // pairs with difference
            // equal to that of
            // minimum difference
            answer++;
    }
 
    // Return the final count
    return answer;
}
 
// Driver Code
int main()
{
    // Given array arr[]
    int arr[] = { 4, 2, 1, 3 };
    int N = (sizeof arr) / (sizeof arr[0]);
 
    // Function Call
    cout << numberofpairs(arr, N) << "\n";
 
    return 0;
}

// Java program for the above
import java.util.Arrays;
class GFG{
  
// Function to return the count of all
// pairs having minimal absolute difference
static int numberofpairs(int []arr, int N)
{
    // Stores the count of pairs
    int answer = 0;
  
    // Sort the array
    Arrays.sort(arr);
  
    // Stores the minimum difference
    // between adjacent pairs
    int minDiff = 10000000;
    for (int i = 0; i < N - 1; i++)
  
        // Update the minimum
        // difference between pairs
        minDiff = Math.min(minDiff,
                           arr[i + 1] - arr[i]);
  
    for (int i = 0; i < N - 1; i++)
    {
        if (arr[i + 1] - arr[i] == minDiff)
  
            // Increase count of
            // pairs with difference
            // equal to that of
            // minimum difference
            answer++;
    }
  
    // Return the final count
    return answer;
}
  
// Driver Code
public static void main(String[] args)
{
    // Given array arr[]
    int arr[] = { 4, 2, 1, 3 };
    int N = arr.length;
  
    // Function Call
    System.out.print(numberofpairs(arr, N));
}
}
 
// This code is contributed by rock_cool

# Python3 program to implement
# the above approach
 
# Function to return the count of all
# pairs having minimal absolute difference
def numberofpairs(arr, N):
     
    # Stores the count of pairs
    answer = 0
     
    # Sort the array
    arr.sort()
     
    # Stores the minimum difference
    # between adjacent pairs
    minDiff = 10000000
    for i in range(0, N - 1):
         
        # Update the minimum
        # difference between pairs
        minDiff = min(minDiff,
                      arr[i + 1] - arr[i])
         
    for i in range(0, N - 1):
        if arr[i + 1] - arr[i] == minDiff:
             
            # Increase count of pairs
            # with difference equal to
            # that of minimum difference
            answer += 1
             
    # Return the final count
    return answer
 
# Driver code
if __name__ == '__main__':
     
    # Given array arr[]
    arr = [ 4, 2, 1, 3 ]
    N = len(arr)
     
    # Function call
    print(numberofpairs(arr,N))
 
# This code is contributed by virusbuddah_

// C# program for the above approach
using System;
class GFG{
 
// Function to return the count of all
// pairs having minimal absolute difference
static int numberofpairs(int []arr, int N)
{
     
    // Stores the count of pairs
    int answer = 0;
 
    // Sort the array
    Array.Sort(arr);
 
    // Stores the minimum difference
    // between adjacent pairs
    int minDiff = 10000000;
    for(int i = 0; i < N - 1; i++)
 
        // Update the minimum
        // difference between pairs
        minDiff = Math.Min(minDiff,
                           arr[i + 1] -
                           arr[i]);
 
    for(int i = 0; i < N - 1; i++)
    {
        if (arr[i + 1] - arr[i] == minDiff)
 
            // Increase count of
            // pairs with difference
            // equal to that of
            // minimum difference
            answer++;
    }
 
    // Return the final count
    return answer;
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given array arr[]
    int []arr = { 4, 2, 1, 3 };
    int N = arr.Length;
 
    // Function Call
    Console.Write(numberofpairs(arr, N));
}
}
 
// This code is contributed by shivanisinghss2110

<script>
 
    // Javascript program for the above approach
     
    // Function to return the count of all
    // pairs having minimal absolute difference
    function numberofpairs(arr, N)
    {
        // Stores the count of pairs
        let answer = 0;
 
        // Sort the array
        arr.sort();
 
        // Stores the minimum difference
        // between adjacent pairs
        let minDiff = Number.MAX_VALUE;
        for (let i = 0; i < N - 1; i++)
 
            // Update the minimum
            // difference between pairs
            minDiff = Math.min(minDiff,
                          arr[i + 1] - arr[i]);
 
        for (let i = 0; i < N - 1; i++) {
 
            if (arr[i + 1] - arr[i] == minDiff)
 
                // Increase count of
                // pairs with difference
                // equal to that of
                // minimum difference
                answer++;
        }
 
        // Return the final count
        return answer;
    }
     
    // Given array arr[]
    let arr = [ 4, 2, 1, 3 ];
    let N = arr.length;
   
    // Function Call
    document.write(numberofpairs(arr, N));
     
</script>

3

Complejidad de tiempo: O(N*log N)  
Espacio auxiliar: O(1)