Dada una array de enteros arr[] de tamaño N , la tarea es encontrar todos los pares distintos que tengan una diferencia absoluta mínima e imprimirlos en orden ascendente .
Ejemplos :
Entrada : arr[] = {4, 2, 1, 3}
Salida : {1, 2}, {2, 3}, {3, 4}
Explicación : la diferencia absoluta mínima entre pares es 1.Entrada : arr[] = {1, 3, 8, 10, 15}
Salida : {1, 3}, {8, 10}
Explicación : La mínima diferencia absoluta entre los pares {1, 3}, {8, 10} es 2
Enfoque : la idea es considerar la diferencia absoluta de los elementos adyacentes de la array ordenada . Siga los pasos a continuación para resolver el problema:
- Ordenar la array dada arr[].
- Compare todos los pares adyacentes en la array ordenada y encuentre la diferencia absoluta mínima entre todos los pares adyacentes.
- Finalmente, imprima todos los pares adyacentes que tengan diferencias iguales a la diferencia mínima absoluta.
A continuación se muestra la implementación del código anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to return all
// pairs having minimal absolute difference
vector<vector<int> > minAbsDiffPairs(vector<int>& arr)
{
vector<vector<int> > ans;
int n = arr.size();
// Sort the array
sort(arr.begin(), arr.end());
// Stores the minimal absolute difference
int minDiff = INT_MAX;
for (int i = 0; i < n - 1; i++)
minDiff = min(minDiff, abs(arr[i] - arr[i + 1]));
for (int i = 0; i < n - 1; i++) {
vector<int> pair;
if (abs(arr[i] - arr[i + 1]) == minDiff) {
pair.push_back(min(arr[i], arr[i + 1]));
pair.push_back(max(arr[i], arr[i + 1]));
ans.push_back(pair);
}
}
return ans;
}
// Driver Code
int main()
{
vector<int> arr = { 4, 2, 1, 3 };
int N = (sizeof arr) / (sizeof arr[0]);
vector<vector<int> > pairs = minAbsDiffPairs(arr);
// Print all pairs
for (auto v : pairs)
cout << v[0] << " " << v[1] << endl;
return 0;
}
Java
// Java program for the above approach
import java.util.ArrayList;
import java.util.Collections;
class GFG
{
// Function to return all
// pairs having minimal absolute difference
static ArrayList<ArrayList<Integer>> minAbsDiffPairs(ArrayList<Integer> arr) {
ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
int n = arr.size();
// Sort the array
Collections.sort(arr);
// Stores the minimal absolute difference
int minDiff = Integer.MAX_VALUE;
for (int i = 0; i < n - 1; i++)
minDiff = Math.min(minDiff, Math.abs(arr.get(i) - arr.get(i + 1)));
for (int i = 0; i < n - 1; i++) {
ArrayList<Integer> pair = new ArrayList<Integer>();
if (Math.abs(arr.get(i) - arr.get(i + 1)) == minDiff) {
pair.add(Math.min(arr.get(i), arr.get(i + 1)));
pair.add(Math.max(arr.get(i), arr.get(i + 1)));
ans.add(pair);
}
}
return ans;
}
// Driver Code
public static void main(String args[]) {
ArrayList<Integer> arr = new ArrayList<Integer>();
arr.add(4);
arr.add(2);
arr.add(1);
arr.add(3);
ArrayList<ArrayList<Integer>> pairs = minAbsDiffPairs(arr);
// Print all pairs
// System.out.println(pairs);
for (ArrayList<Integer> v : pairs) {
for (int w : v)
System.out.print(w + " ");
System.out.println("");
}
}
}
// This code is contributed by saurabh_jaiswal.
Python3
# Python3 program for the above approach
import math as Math
# Function to return all pairs having
# minimal absolute difference
def minAbsDiffPairs(arr):
ans = []
n = len(arr)
# Sort the array
arr.sort()
# Stores the minimal absolute difference
minDiff = 10 ** 9
for i in range(n - 1):
minDiff = min(minDiff, Math.fabs(arr[i] -
arr[i + 1]))
for i in range(n - 1):
pair = []
if (Math.fabs(arr[i] - arr[i + 1]) == minDiff):
pair.append(min(arr[i], arr[i + 1]))
pair.append(max(arr[i], arr[i + 1]))
ans.append(pair)
return ans
# Driver Code
arr = [ 4, 2, 1, 3 ]
N = len(arr)
pairs = minAbsDiffPairs(arr)
# Print all pairs
for v in pairs:
print(f"{v[0]} {v[1]}")
# This code is contributed by gfgking
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to return all
// pairs having minimal Absolute difference
static List<List<int>> minAbsDiffPairs(List<int> arr) {
List<List<int>> ans = new List<List<int>>();
int n = arr.Count;
// Sort the array
arr.Sort();
// Stores the minimal Absolute difference
int minDiff = int.MaxValue;
for (int i = 0; i < n - 1; i++)
minDiff = Math.Min(minDiff, Math.Abs(arr[i] - arr[i + 1]));
for (int i = 0; i < n - 1; i++) {
List<int> pair = new List<int>();
if (Math.Abs(arr[i] - arr[i + 1]) == minDiff) {
pair.Add(Math.Min(arr[i], arr[i + 1]));
pair.Add(Math.Max(arr[i], arr[i + 1]));
ans.Add(pair);
}
}
return ans;
}
// Driver Code
public static void Main()
{
List<int> arr = new List<int>();
arr.Add(4);
arr.Add(2);
arr.Add(1);
arr.Add(3);
List<List<int>> pairs = minAbsDiffPairs(arr);
// Print all pairs
// System.out.println(pairs);
foreach (List<int> v in pairs)
{
foreach (int w in v)
Console.Write(w + " ");
Console.WriteLine("");
}
}
}
// This code is contributed by saurabh_jaiswal.
Javascript
<script>
// JavaScript code for the above approach
// Function to return all
// pairs having minimal absolute difference
function minAbsDiffPairs(arr)
{
let ans = [];
let n = arr.length;
// Sort the array
arr.sort(function (a, b) { return a - b })
// Stores the minimal absolute difference
let minDiff = Number.MAX_VALUE;
for (let i = 0; i < n - 1; i++)
minDiff = Math.min(minDiff, Math.abs(arr[i] - arr[i + 1]));
for (let i = 0; i < n - 1; i++) {
let pair = [];
if (Math.abs(arr[i] - arr[i + 1]) == minDiff) {
pair.push(Math.min(arr[i], arr[i + 1]));
pair.push(Math.max(arr[i], arr[i + 1]));
ans.push(pair);
}
}
return ans;
}
// Driver Code
let arr = [4, 2, 1, 3];
let N = arr.length;
let pairs = minAbsDiffPairs(arr);
// Print all pairs
for (let v of pairs)
document.write(v[0] + " " + v[1] + '<br>')
// This code is contributed by Potta Lokesh
</script>
Producción
1 2 2 3 3 4
Complejidad de Tiempo : O(NlogN)
Espacio Auxiliar : O(N), ya que se ha tomado N espacio extra.