Dada una array arr[] que consta de N enteros, la tarea es encontrar el número máximo de pares de elementos de la array de manera que cada par tenga un elemento diferente y cada elemento de la array pueda existir en un solo par.
Ejemplos:
Entrada: arr[] = {4, 5, 4, 5, 4}
Salida: 2
Explicación:
Puede haber 2 formas de pares de la array dada, es decir, {{4, 5}, {4, 5}}. Por lo tanto, imprime 2.Entrada: arr[] = {2, 3, 2, 1, 3, 1}
Salida: 3
Enfoque: el problema dado se puede resolver almacenando la frecuencia de los elementos de la array y generando los pares usando los dos números de frecuencia más altos. Esta idea se puede implementar usando Priority Queue . Siga los pasos a continuación para resolver el problema:
- Inicialice un Map , digamos M que almacena la frecuencia de los elementos de la array.
- Inicialice una cola de prioridad , digamos, PQ , para implementar MaxHeap e inserte todas las frecuencias en ella.
- Inicialice una variable, digamos, cuente como 0 que almacene el recuento máximo de pares resultantes.
- Recorra la cola de prioridad PQ hasta que su tamaño sea mayor que 1 y realice los siguientes pasos:
- Haga estallar los dos elementos superiores del PQ .
- Disminuya el valor de un elemento reventado en 1 e inserte ambos elementos nuevamente en el PQ .
- Incrementa el valor de count en 1 .
- Después de completar los pasos anteriores, imprima el recuento de valores como resultado.
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 count the maximum number
// of pairs having different element
// from the given array
int maximumPairs(int a[], int n)
{
// Stores the frequency of
// array element
map<int, int> freq;
// Stores maximum count of pairs
int count = 0;
// Increasing the frequency of
// every element
for (int i = 0; i < n; ++i)
freq[a[i]]++;
// Stores the frequencies of array
// element from highest to lowest
priority_queue<int> pq;
for (auto itr = freq.begin();
itr != freq.end();
itr++) {
// Pushing the frequencies to
// the priority queue
pq.push(itr->second);
}
// Iterate until size of PQ > 1
while (pq.size() > 1) {
// Stores the top two element
int freq1 = pq.top();
pq.pop();
int freq2 = pq.top();
pq.pop();
// Form the pair between the
// top two pairs
count++;
// Decrement the frequencies
freq1--;
freq2--;
// Insert updated frequencies
// if it is greater than 0
if (freq1 > 0)
pq.push(freq1);
if (freq2 > 0)
pq.push(freq2);
}
// Return the total count of
// resultant pairs
return count;
}
// Driver Code
int main()
{
int arr[] = { 4, 2, 4, 1, 4, 3 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << maximumPairs(arr, N);
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
import java.util.*;
class GFG {
public static int maximumPairs(int[] a, int n)
{
// Stores the frequency of
// array element
HashMap<Integer, Integer> freq
= new HashMap<Integer, Integer>();
// Stores maximum count of pairs
int count = 0;
// Increasing the frequency of
// every element
for (int i = 0; i < n; i++) {
int c = a[i];
if (freq.containsKey(c)) {
freq.put(c, freq.get(c) + 1);
}
else {
freq.put(c, 1);
}
}
// Stores the frequencies of array
// element from highest to lowest
PriorityQueue<Integer> pq
= new PriorityQueue<Integer>();
for (int i = 0;i<n;i++) {
// Pushing the frequencies to
// the priority queue
if(freq.containsKey(a[i])){
pq.add(freq.get(a[i]));
freq.remove(a[i]);
}
}
// Iterate until size of PQ > 1
while (pq.size() > 1) {
// Stores the top two element
int freq1 = pq.poll();
int freq2 = pq.poll();
// Form the pair between the
// top two pairs
count++;
// Decrement the frequencies
freq1--;
freq2--;
// Insert updated frequencies
// if it is greater than 0
if (freq1 > 0)
pq.add(freq1);
if (freq2 > 0)
pq.add(freq2);
}
// Return the total count of
// resultant pairs
return count;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 4, 2, 4, 1, 4, 3 };
int N = 6;
System.out.println(maximumPairs(arr, N));
}
}
// This code is contributed by maddler.
Python3
# python 3 program for the above approach
# Function to count the maximum number
# of pairs having different element
# from the given array
def maximumPairs(a, n):
# Stores the frequency of
# array element
freq = {}
# Stores maximum count of pairs
count = 0
# Increasing the frequency of
# every element
for i in range(n):
if a[i] in freq:
freq[a[i]] += 1
else:
freq[a[i]] = 1
# Stores the frequencies of array
# element from highest to lowest
pq = []
for key,value in freq.items():
# Pushing the frequencies to
# the priority queue
pq.append(value)
pq.sort()
# Iterate until size of PQ > 1
while (len(pq) > 1):
# Stores the top two element
freq1 = pq[len(pq)-1]
pq = pq[:-1]
freq2 = pq[len(pq)-1]
pq = pq[:-1]
# Form the pair between the
# top two pairs
count += 1
# Decrement the frequencies
freq1 -= 1
freq2 -= 1
# Insert updated frequencies
# if it is greater than 0
if (freq1 > 0):
pq.append(freq1)
if (freq2 > 0):
pq.append(freq2)
pq.sort()
# Return the total count of
# resultant pairs
return count
# Driver Code
if __name__ == '__main__':
arr = [4, 2, 4, 1, 4, 3]
N = len(arr)
print(maximumPairs(arr, N))
# This code is contributed by ipg2016107.
C#
/*package whatever //do not write package name here */
using System;
using System.Collections.Generic;
public class GFG {
public static int maximumPairs(int[] a, int n) {
// Stores the frequency of
// array element
Dictionary<int, int> freq = new Dictionary<int, int>();
// Stores maximum count of pairs
int count = 0;
// Increasing the frequency of
// every element
for (int i = 0; i < n; i++) {
int c = a[i];
if (freq.ContainsKey(c)) {
freq = freq + 1;
} else {
freq.Add(c, 1);
}
}
// Stores the frequencies of array
// element from highest to lowest
Queue<int> pq = new Queue<int>();
for (int i = 0; i < n; i++) {
// Pushing the frequencies to
// the priority queue
if (freq.ContainsKey(a[i])) {
pq.Enqueue(freq[a[i]]);
freq.Remove(a[i]);
}
}
// Iterate until size of PQ > 1
while (pq.Count > 1) {
// Stores the top two element
int freq1 = pq.Dequeue();
int freq2 = pq.Dequeue();
// Form the pair between the
// top two pairs
count++;
// Decrement the frequencies
freq1--;
freq2--;
// Insert updated frequencies
// if it is greater than 0
if (freq1 > 0)
pq.Enqueue(freq1);
if (freq2 > 0)
pq.Enqueue(freq2);
}
// Return the total count of
// resultant pairs
return count;
}
// Driver Code
public static void Main(String[] args) {
int []arr = { 4, 2, 4, 1, 4, 3 };
int N = 6;
Console.WriteLine(maximumPairs(arr, N));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program for the above approach
// Function to count the maximum number
// of pairs having different element
// from the given array
function maximumPairs(a, n)
{
// Stores the frequency of
// array element
var freq = new Map();
// Stores maximum count of pairs
var count = 0;
// Increasing the frequency of
// every element
for (var i = 0; i < n; ++i)
{
if(freq.has(a[i]))
freq.set(a[i], freq.get(a[i])+1)
else
freq.set(a[i],1)
}
// Stores the frequencies of array
// element from highest to lowest
var pq = [...freq.values()];
pq.sort((a,b)=>a-b);
// Iterate until size of PQ > 1
while (pq.length > 1) {
// Stores the top two element
var freq1 = pq[pq.length-1];
pq.pop();
var freq2 = pq[pq.length-1];
pq.pop();
// Form the pair between the
// top two pairs
count++;
// Decrement the frequencies
freq1--;
freq2--;
// Insert updated frequencies
// if it is greater than 0
if (freq1 > 0)
pq.push(freq1);
if (freq2 > 0)
pq.push(freq2);
pq.sort((a,b)=>a-b);
}
// Return the total count of
// resultant pairs
return count;
}
// Driver Code
var arr = [4, 2, 4, 1, 4, 3 ];
var N = arr.length;
document.write( maximumPairs(arr, N));
// This code is contributed by rrrtnx.
</script>
Producción
3
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)
Otro enfoque:
Este problema también se puede resolver simplemente almacenando la frecuencia de cada elemento en una array. Después de eso, necesitamos encontrar la frecuencia máxima de un elemento en la array dada. Se confirma que un par no puede tener los mismos valores. Supongamos que tenemos los elementos arr[]={1,1,1,1,2} entonces se formará un par ya que hay dos valores diferentes presentes en la array. Por lo tanto, no se pueden formar pares si nos quedamos con el elemento que tiene los mismos valores.
A continuación se muestra la implementación:
C++
#include <bits/stdc++.h>
using namespace std;
int main()
{
int arr[] = { 4, 2, 4, 1, 4, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
int maxi = 0, remain, ans;
// stores the frequency array
map<int, int> freq;
for (int i = 0; i < n; i++) {
freq[arr[i]]++;
}
for (auto it : freq) {
// maxi stores the maximum
// frequency of an element
maxi = max(maxi, it.second);
}
// it stores the sum of all the frequency
// other than the element which has maximum frequency
remain = n - maxi;
if (maxi >= remain) {
// there will be always zero
// or more element
// which will not participate in making pairs
ans = remain;
}
else {
// if n is odd then except one element
// we can always form pair for every element
// if n is even then all the elements can form pair
ans = n / 2;
}
cout << ans;
freq.clear();
return 0;
}
Java
import java.util.*;
class GFG{
public static void main(String[] args)
{
int arr[] = { 4, 2, 4, 1, 4, 3 };
int n = arr.length;
int maxi = 0, remain, ans;
// stores the frequency array
HashMap<Integer,Integer> freq = new HashMap<>();
for (int i = 0; i < n; i++) {
if(freq.containsKey(arr[i])){
freq.put(arr[i], freq.get(arr[i])+1);
}
else{
freq.put(arr[i], 1);
}
}
for (Map.Entry<Integer,Integer> it : freq.entrySet())
{
// maxi stores the maximum
// frequency of an element
maxi = Math.max(maxi, it.getValue());
}
// it stores the sum of all the frequency
// other than the element which has maximum frequency
remain = n - maxi;
if (maxi >= remain)
{
// there will be always zero
// or more element
// which will not participate in making pairs
ans = remain;
}
else
{
// if n is odd then except one element
// we can always form pair for every element
// if n is even then all the elements can form pair
ans = n / 2;
}
System.out.print(ans);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python program for the above approach arr = [ 4, 2, 4, 1, 4, 3 ] n = len(arr) maxi = 0 # stores the frequency array freq= dict() for i in range(n): if arr[i] in freq.keys(): freq[arr[i]] += 1 else: freq[arr[i]] = 1 for it in freq: # maxi stores the maximum # frequency of an element maxi = max(maxi, freq[it]) # it stores the sum of all the frequency # other than the element which has maximum frequency remain = n - maxi if(maxi >= remain): # there will be always zero # or more element # which will not participate in making pairs ans = remain else: # if n is odd then except one element # we can always form pair for every element # if n is even then all the elements can form pair ans = n//2 print(ans) freq.clear() # This code is contributed by Pushpesh Raj
C#
using System;
using System.Collections;
using System.Collections.Generic;
class GFG
{
public static void Main()
{
int []arr = { 4, 2, 4, 1, 4, 3 };
int n = arr.Length;
int maxi = 0, remain, ans;
// stores the frequency array
Dictionary<int, int> freq =
new Dictionary<int, int>();
for (int i = 0; i < n; i++) {
if (freq.ContainsKey(arr[i]))
{
freq[arr[i]] = freq[arr[i]] + 1;
}
else
{
freq.Add(arr[i], 1);
}
}
foreach (KeyValuePair<int, int> it in freq)
{
// maxi stores the maximum
// frequency of an element
maxi = Math.Max(maxi, it.Value);
}
// it stores the sum of all the frequency
// other than the element which has maximum frequency
remain = n - maxi;
if (maxi >= remain)
{
// there will be always zero
// or more element
// which will not participate in making pairs
ans = remain;
}
else
{
// if n is odd then except one element
// we can always form pair for every element
// if n is even then all the elements can form pair
ans = n / 2;
}
Console.Write(ans);
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
let arr = [4, 2, 4, 1, 4, 3];
let n = arr.length;
let maxi = 0,
remain,
ans;
// stores the frequency array
let freq = new Map();
for (let i = 0; i < n; i++) {
if (freq.has(arr[i])) {
freq.set(arr[i], freq.get(arr[i]) + 1);
} else {
freq.set(arr[i], 1);
}
}
for (let it of freq)
{
// maxi stores the maximum
// frequency of an element
maxi = Math.max(maxi, it[1]);
}
// it stores the sum of all the frequency
// other than the element which has maximum frequency
remain = n - maxi;
if (maxi >= remain)
{
// there will be always zero
// or more element
// which will not participate in making pairs
ans = remain;
}
else
{
// if n is odd then except one element
// we can always form pair for every element
// if n is even then all the elements can form pair
ans = Math.floor(n / 2);
}
document.write(ans);
freq.clear();
// This code is contributed by gfgking.
</script>
Producción
3
La complejidad temporal de este enfoque es O(N) ya que estamos atravesando todos los elementos para formar la array de frecuencias.
El espacio auxiliar es O(N).
Publicación traducida automáticamente
Artículo escrito por harshsrivastava9795 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA