Número máximo de trillizos únicos de modo que cada elemento se seleccione solo una vez

Dada una array arr[] de tamaño, N . Encuentre el número máximo de tripletes que se pueden formar usando elementos de array de modo que todos los elementos en cada triplete sean diferentes. Imprime el número máximo de trillizos posibles junto con una lista de los trillizos.
Nota: Cada elemento de la array puede pertenecer solo a 1 triplete.
Ejemplos: 

Entrada: arr[] = {2, 2, 3, 3, 4, 4, 4, 4, 5} 
Salida: 
Número máximo de triples posibles: 2 
2 3 4 
3 4 5 
Explicación: 
Podemos formar como máximo 2 triples usando el arreglo dado tal que cada triple contiene diferentes elementos. 
Entrada: arr[] = {1, 2, 3, 4, 5, 6, 7 } 
Salida: 
Número máximo de triples posibles: 2 
5 6 7 
2 3 4 
Explicación: 
Podemos formar como máximo 2 triples usando la array dada tal que cada triple contiene elementos diferentes. 

Enfoque ingenuo: la idea es ejecutar tres bucles anidados para generar todos los tripletes y, para cada triplete, verificar si son distintos por pares y también verificar si cada elemento de la array pertenece exactamente a 1 triplete.
Complejidad de Tiempo: O(N ³ ) 
Espacio Auxiliar: O(1) 
Enfoque Eficiente: El problema puede resolverse con Enfoque Codicioso y seguir tomando trillizos que tengan una frecuencia máxima. A continuación se muestran los pasos: 
 

• Almacena la frecuencia de todos los números en un Mapa .
• Haga una cola de prioridad máxima y almacene pares en ella, donde el primer elemento del par es la frecuencia de algún elemento y el segundo elemento del par es el elemento mismo.
• Ahora extraiga repetidamente los 3 elementos principales de la cola de prioridad, haga trillizos usando esos 3 elementos, disminuya su frecuencia en 1 y vuelva a insertar elementos en la cola de prioridad usando la frecuencia mayor que 0.

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 that finds maximum number
// of triplets with different elements
void findTriplets(int ar[], int n)
{
 
    // Map M will store the frequency
    // of each element in the array
    unordered_map<int, int> mp;
 
    for (int x = 0; x < n; x++)
        mp[ar[x]]++;
 
    // Priority queue of pairs
    // {frequency, value}
    priority_queue<pair<int, int> > pq;
 
    for (auto& pa : mp)
        pq.push({ pa.second, pa.first });
 
    // ans will store possible triplets
    vector<array<int, 3> > ans;
 
    while (pq.size() >= 3) {
 
        // Extract top 3 elements
        pair<int, int> ar[3];
        for (int x = 0; x < 3; x++) {
            ar[x] = pq.top();
            pq.pop();
        }
 
        // Make a triplet
        ans.push_back({ ar[0].second,
                        ar[1].second,
                        ar[2].second });
 
        // Decrease frequency and push
        // back into priority queue if
        // non-zero frequency
        for (int x = 0; x < 3; x++) {
            ar[x].first--;
            if (ar[x].first)
                pq.push(ar[x]);
        }
    }
 
    // Print the triplets
    cout << "Maximum number of "
         << "possible triples: ";
    cout << ans.size() << endl;
 
    for (auto& pa : ans) {
 
        // Print the triplets
        for (int v : pa)
            cout << v << " ";
        cout << endl;
    }
}
 
// Driver Code
int main()
{
    // Given array arr[]
    int arr[] = { 2, 2, 3, 3, 4, 4, 4, 4, 5 };
 
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    findTriplets(arr, n);
    return 0;
}

// Java program for the
// above approach
import java.util.*;
import java.lang.*;
class GFG{
 
static class pair
{
  int first, second;
  pair(int first, int second)
  {
    this.first = first;
    this.second = second;
  }
}
 
// Function that finds maximum
// number of triplets with
// different elements
static void findTriplets(int arr[],
                         int n)
{
  // Map M will store the frequency
  // of each element in the array
  Map<Integer,
      Integer> mp = new HashMap<>();
 
  for (int x = 0; x < n; x++)
    mp.put(arr[x],
    mp.getOrDefault(arr[x], 0) + 1);
 
  // Priority queue of pairs
  // {frequency, value}
  PriorityQueue<pair> pq =
          new PriorityQueue<>((a, b) ->
                               a.first -
                               b.first);
 
  for (Map.Entry<Integer,
                 Integer> k : mp.entrySet())
    pq.add(new pair(k.getValue(),
                    k.getKey()));
 
  // ans will store possible
  // triplets
  ArrayList<List<Integer> > ans =
                 new ArrayList<>();
 
  while (pq.size() >= 3)
  {
    // Extract top 3 elements
    pair[] ar = new pair[3];
    for (int x = 0; x < 3; x++)
    {
      ar[x] = pq.peek();
      pq.poll();
    }
 
    // Make a triplet
    ans.add(Arrays.asList(ar[0].second,
                          ar[1].second,
                          ar[2].second));
 
    // Decrease frequency and push
    // back into priority queue if
    // non-zero frequency
    for (int x = 0; x < 3; x++)
    {
      ar[x].first--;
      if (ar[x].first != 0)
        pq.add(ar[x]);
    }
  }
 
  // Print the triplets
  System.out.println("Maximum number of " +
                     "possible triples: " +
                      ans.size());
 
  for (List<Integer> pa : ans)
  {
    // Print the triplets
    for (Integer v : pa)
      System.out.print(v + " ");
 
    System.out.println();
  }
}
 
// Driver function
public static void main(String[] args)
{
  // Given array arr[]
  int arr[] = {2, 2, 3, 3, 4,
               4, 4, 4, 5};
 
  int n = arr.length;
 
  // Function Call
  findTriplets(arr, n);
}
}
 
// This code is contributed by offbeat

# Python3 program for the above approach
from functools import cmp_to_key
def mycmp(a, b):
           
    if(a[0] == b[0]):
        return a[1] - b[1]
    return a[0] - b[0]
 
# Function that finds maximum number
# of triplets with different elements
def findTriplets(ar, n):
 
    # Map M will store the frequency
    # of each element in the array
    mp = {}
 
    for x in range(n):
 
        if(ar[x] in mp):
          mp[ar[x]] += 1
        else:
            mp[ar[x]] = 1
 
    # Priority queue of pairs
    # {frequency, value}
    pq = []
 
    for pa,pa2 in mp.items():
        pq.append([pa2, pa])
 
    # ans will store possible triplets
    ans = []
    pq.sort(key = cmp_to_key(mycmp))
 
    while (len(pq) >= 3):
 
        # Extract top 3 elements
        ar = [[0 for i in range(2)]for j in range(3)]
        for x in range(3):
            ar[x] = pq[len(pq)-1]
            pq.pop()
 
        # Make a triplet
        ans.append([ar[0][1],ar[1][1],ar[2][1]])
 
        # Decrease frequency and append
        # back into priority queue if
        # non-zero frequency
        for x in range(3):
            ar[x][0] -= 1
            if (ar[x][0]):
                pq.append(ar[x])
         
        pq.sort(key = cmp_to_key(mycmp))
 
    # Print the triplets
    print("Maximum number of " + "possible triples:",end=" ")
    print(len(ans))
 
    for pa in ans:
 
        # Print the triplets
        for v in pa:
            print(v ,end = " ")
        print()
     
 
# Driver Code
# Given array arr[]
arr = [2, 2, 3, 3, 4, 4, 4, 4, 5]
n = len(arr)
 
# Function Call
findTriplets(arr, n)
 
# This code is contributed by Shinjan Patra

// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
 
  // Function that finds maximum number
  // of triplets with different elements
  static void findTriplets(int[] arr, int n)
  {
 
    // Map M will store the frequency
    // of each element in the array
    Dictionary<int, int> mp = new Dictionary<int, int>();
    for (int x = 0; x < n; x++)
    {
      if(mp.ContainsKey(arr[x]))
      {
        mp[arr[x]]++;
      }
      else
      {
        mp[arr[x]] = 1;
      }
    }
 
    // Priority queue of pairs
    // {frequency, value}
    List<Tuple<int, int> > pq = new List<Tuple<int,int>>();
    int cnt = 0;
    foreach(KeyValuePair<int, int> pa in mp)
      pq.Add(new Tuple<int,int>(pa.Value, pa.Key));
 
    // ans will store possible triplets
    List<List<int>> ans = new List<List<int>>();
    pq.Sort();
    pq.Reverse();
    while (pq.Count >= 3)
    {
 
      // Extract top 3 elements
      Tuple<int, int>[] ar = new Tuple<int,int>[3];
      for (int x = 0; x < 3; x++)
      {
        ar[x] = pq[0];
        pq.RemoveAt(0);
      }
      ans.Add(new List<int>());
      ans[cnt].Add(ar[0].Item2);
      ans[cnt].Add(ar[1].Item2);
      ans[cnt].Add(ar[2].Item2);
 
      // Decrease frequency and push
      // back into priority queue if
      // non-zero frequency
      for (int x = 0; x < 3; x++)
      {
        ar[x] = new Tuple<int,int>(ar[x].Item1 - 1, ar[x].Item2);
        if (ar[x].Item1 != 0)
        {
          pq.Add(ar[x]);
          pq.Sort();
          pq.Reverse();
        }
      }
      cnt++;
    }
 
    // Print the triplets
    Console.Write("Maximum number of possible triples: ");
    Console.WriteLine(ans.Count);
    foreach(List<int> pa in ans)
    {
 
      // Print the triplets
      foreach(int v in pa)
        Console.Write(v + " ");
      Console.WriteLine();
    }
  }
 
  // Driver code
  static void Main()
  {
 
    // Given array arr[]
    int[] arr = { 2, 2, 3, 3, 4, 4, 4, 4, 5 };
 
    int n = arr.Length;
 
    // Function Call
    findTriplets(arr, n);
  }
}
 
// This code is contributed by divyeshrabadiya07.

<script>
 
// Javascript program for the above approach
 
// Function that finds maximum number
// of triplets with different elements
function findTriplets(ar, n)
{
 
    // Map M will store the frequency
    // of each element in the array
    var mp = new Map();
 
    for (var x = 0; x < n; x++)
    {
        if(mp.has(ar[x]))
          mp.set(ar[x], mp.get(ar[x])+1)
        else
            mp.set(ar[x],1)
    }
 
    // Priority queue of pairs
    // {frequency, value}
    var pq = [];
 
    for(var pa of mp)
        pq.push([pa[1], pa[0]]);
 
    // ans will store possible triplets
    var ans = [];
    pq.sort((a,b)=>{
          if(a[0]==b[0])
            return a[1]-b[1];
         return a[0]-b[0];
      });
 
    while (pq.length >= 3) {
 
        // Extract top 3 elements
        var ar = Array.from(Array(3), ()=>Array(2).fill(0));
        for (var x = 0; x < 3; x++) {
            ar[x] = pq[pq.length-1];
            pq.pop();
        }
 
        // Make a triplet
        ans.push([ar[0][1],
                        ar[1][1],
                        ar[2][1] ]);
 
        // Decrease frequency and push
        // back into priority queue if
        // non-zero frequency
        for (var x = 0; x < 3; x++) {
            ar[x][0]--;
            if (ar[x][0])
                pq.push(ar[x]);
        }
      pq.sort((a,b)=>{
          if(a[0]==b[0])
            return a[1]-b[1];
         return a[0]-b[0];
      });
    }
 
    // Print the triplets
    document.write("Maximum number of "
          + "possible triples: ");
    document.write(ans.length + "<br>");
 
    for (var pa of ans) {
 
        // Print the triplets
        for (var v of pa)
            document.write( v + " ");
        document.write("<br>");
    }
}
 
// Driver Code
// Given array arr[]
var arr = [2, 2, 3, 3, 4, 4, 4, 4, 5];
var n = arr.length;
 
// Function Call
findTriplets(arr, n);
 
// This code is contributed by noob20000
</script>

Maximum number of possible triples: 2
4 3 2 
4 5 3

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