Dada una array arr[] de N enteros, la tarea es encontrar la máxima diferencia absoluta entre distintos elementos de la array.
Ejemplos:
Entrada: arr[] = {12, 10, 9, 45, 2, 10, 10, 45, 10}
Salida: 10
Explicación:
Los distintos elementos de una array dada son 12, 9, 2.
Por lo tanto, la máxima diferencia absoluta entre ellos es (12 – 2) = 10.Entrada: arr[] = {2, -1, 10, 3, -2, -1, 10}
Salida: 5
Explicación:
Los distintos elementos de una array dada son 2, 3, -2.
Por lo tanto, la máxima diferencia absoluta entre ellos es (3 – (-2)) = 5.
Enfoque ingenuo: el enfoque ingenuo es almacenar el elemento distinto en la array dada en una array temp[] e imprimir la diferencia del elemento máximo y mínimo de la array temp[] .
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque eficiente: el enfoque ingenuo anterior se puede optimizar utilizando Hashing . A continuación se muestran los pasos:
- Almacene la frecuencia de cada elemento de la array arr[] en un HashMap .
- Ahora encuentre el valor máximo y mínimo de la array cuya frecuencia es 1 utilizando el HashMap creado anteriormente.
- Imprime la diferencia entre el valor máximo y mínimo obtenido en el paso anterior.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum
// absolute difference between
// distinct elements in arr[]
int MaxAbsDiff(int arr[], int n)
{
// Map to store each element
// with their occurrence in array
unordered_map<int, int> map;
// maxElement and minElement to
// store maximum and minimum
// distinct element in arr[]
int maxElement = INT_MIN;
int minElement = INT_MAX;
// Traverse arr[] and update each
// element frequency in Map
for(int i = 0; i < n; i++)
{
map[arr[i]]++;
}
// Traverse Map and check if
// value of any key appears 1
// then update maxElement and
// minElement by that key
for(auto itr = map.begin();
itr != map.end(); itr++)
{
if (itr -> second == 1)
{
maxElement = max(maxElement,
itr -> first);
minElement = min(minElement,
itr -> first);
}
}
// Return absolute difference of
// maxElement and minElement
return abs(maxElement - minElement);
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 12, 10, 9, 45, 2,
10, 10, 45, 10 };
int n = sizeof(arr) / sizeof(arr[0]);
// Function call
cout << MaxAbsDiff(arr, n) << "\n";
return 0;
}
// This code is contributed by akhilsaini
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to find the maximum
// absolute difference between
// distinct elements in arr[]
static int MaxAbsDiff(int[] arr, int n)
{
// HashMap to store each element
// with their occurrence in array
Map<Integer, Integer> map
= new HashMap<>();
// maxElement and minElement to
// store maximum and minimum
// distinct element in arr[]
int maxElement = Integer.MIN_VALUE;
int minElement = Integer.MAX_VALUE;
// Traverse arr[] and update each
// element frequency in HashMap
for (int i = 0; i < n; i++) {
map.put(arr[i],
map.getOrDefault(arr[i], 0)
+ 1);
}
// Traverse HashMap and check if
// value of any key appears 1
// then update maxElement and
// minElement by that key
for (Map.Entry<Integer, Integer> k :
map.entrySet()) {
if (k.getValue() == 1) {
maxElement
= Math.max(maxElement,
k.getKey());
minElement
= Math.min(minElement,
k.getKey());
}
}
// Return absolute difference of
// maxElement and minElement
return Math.abs(maxElement
- minElement);
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int[] arr = { 12, 10, 9, 45, 2,
10, 10, 45, 10 };
int n = arr.length;
// Function Call
System.out.println(MaxAbsDiff(arr, n));
}
}
Python3
# Python3 program for # the above approach import sys from collections import defaultdict # Function to find the maximum # absolute difference between # distinct elements in arr[] def MaxAbsDiff(arr, n): # HashMap to store each element # with their occurrence in array map = defaultdict (int) # maxElement and minElement to # store maximum and minimum # distinct element in arr[] maxElement = -sys.maxsize - 1 minElement = sys.maxsize # Traverse arr[] and update each # element frequency in HashMap for i in range (n): map[arr[i]] += 1 # Traverse HashMap and check if # value of any key appears 1 # then update maxElement and # minElement by that key for k in map: if (map[k] == 1): maxElement = max(maxElement, k) minElement = min(minElement, k) # Return absolute difference of # maxElement and minElement return abs(maxElement - minElement) # Driver Code if __name__ == "__main__": # Given array arr[] arr = [12, 10, 9, 45, 2, 10, 10, 45, 10] n = len( arr) # Function Call print(MaxAbsDiff(arr, n)) # This code is contributed by Chitranayal
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the maximum
// absolute difference between
// distinct elements in []arr
static int MaxAbsDiff(int[] arr, int n)
{
// Dictionary to store each element
// with their occurrence in array
Dictionary<int,
int> map = new Dictionary<int,
int>();
// maxElement and minElement to
// store maximum and minimum
// distinct element in []arr
int maxElement = int.MinValue;
int minElement = int.MaxValue;
// Traverse []arr and update each
// element frequency in Dictionary
for(int i = 0; i < n; i++)
{
if(map.ContainsKey(arr[i]))
map[arr[i]] = map[arr[i]] + 1;
else
map.Add(arr[i], 1);
}
// Traverse Dictionary and check if
// value of any key appears 1
// then update maxElement and
// minElement by that key
foreach (KeyValuePair<int, int> k in map)
{
if (k.Value == 1)
{
maxElement = Math.Max(maxElement,
k.Key);
minElement = Math.Min(minElement,
k.Key);
}
}
// Return absolute difference of
// maxElement and minElement
return Math.Abs(maxElement - minElement);
}
// Driver Code
public static void Main(String[] args)
{
// Given array []arr
int[] arr = { 12, 10, 9, 45, 2,
10, 10, 45, 10 };
int n = arr.Length;
// Function call
Console.WriteLine(MaxAbsDiff(arr, n));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript program for the above approach
// Function to find the maximum
// absolute difference between
// distinct elements in arr[]
function MaxAbsDiff(arr, n)
{
// Map to store each element
// with their occurrence in array
var map = new Map();
// maxElement and minElement to
// store maximum and minimum
// distinct element in arr[]
var maxElement = -1000000000;
var minElement = 1000000000;
// Traverse arr[] and update each
// element frequency in Map
for(var i = 0; i < n; i++)
{
if(map.has(arr[i]))
map.set(arr[i], map.get(arr[i])+1)
else
map.set(arr[i], 1);
}
// Traverse Map and check if
// value of any key appears 1
// then update maxElement and
// minElement by that key
map.forEach((value, key) => {
if (value == 1)
{
maxElement = Math.max(maxElement,
key);
minElement = Math.min(minElement,
key);
}
});
// Return absolute difference of
// maxElement and minElement
return Math.abs(maxElement - minElement);
}
// Driver Code
// Given array arr[]
var arr = [12, 10, 9, 45, 2,
10, 10, 45, 10 ];
var n = arr.length;
// Function call
document.write( MaxAbsDiff(arr, n));
// This code is contributed by famously.
</script>
Producción:
10
Complejidad temporal: O(N)
Espacio auxiliar: O(N)