Dividir igualmente en dos conjuntos de modo que un conjunto tenga el máximo de elementos distintos

Hay dos procesos P1 y P2, y N recursos donde N es un número par. Hay una array de tamaño N y arr[i] representa el tipo de i-ésimo recurso. Puede haber más de una instancia de un recurso. Debe dividir estos recursos por igual entre P1 y P2 de modo que el número máximo de recursos distintos se asignan a P2. Imprime el número máximo de recursos distintos asignados a P2.

Ejemplos: 

Entrada: arr[] = [1, 1, 2, 2, 3, 3] 
Salida: 3 
Explicación: 
Hay tres tipos diferentes de recursos (1, 2 y 3), y dos para cada tipo. Distribución óptima: el proceso P1 tiene recursos [1, 2, 3] y el proceso P2 también tiene regalos [1, 2, 3]. El proceso p2 tiene 3 recursos distintos.

Entrada: arr[] = [1, 1, 2, 1, 3, 4] 
Salida: 3 
Explicación: 
Hay tres tipos diferentes de recursos (1, 2, 3, 4), 3 instancias de 1 y únicas instancias únicas de recurso 2, 3, 4. Distribución óptima: el proceso P1 tiene recursos [1, 1, 1] y el proceso P2 tiene regalos [2, 3, 4]. 
El proceso p2 tiene 3 recursos distintos. 
 

Enfoque 1 (usando la clasificación): 

1. Ordenar la array de recursos.
2. Descubra los elementos que son únicos comparando los elementos adyacentes de la array ordenada. Supongamos que el conteo contiene el número distinto de recursos en la array.
3. Devuelve el mínimo de cuenta y N/2.

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

// C++ program to equally divide n elements
// into two sets such that second set has
// maximum distinct elements.
#include <algorithm>
#include <iostream>
using namespace std;
 
int distribution(int arr[], int n)
{
    sort(arr, arr + n);
    int count = 1;
    for (int i = 1; i < n; i++)
        if (arr[i] > arr[i - 1])
            count++;
     
    return min(count, n / 2);
}
 
// Driver code
int main()
{
    int arr[] = { 1, 1, 2, 1, 3, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << distribution(arr, n) << endl;
    return 0;
}

// Java program to equally divide n elements
// into two sets such that second set has
// maximum distinct elements.
import java.util.*;
class Geeks {
     
static int distribution(int arr[], int n)
{
    Arrays.sort(arr);
    int count = 1;
    for (int i = 1; i < n; i++)
        if (arr[i] > arr[i - 1])
            count++;
     
    return Math.min(count, n / 2);
}
 
// Driver code
public static void main(String args[])
{
    int arr[] = { 1, 1, 2, 1, 3, 4 };
    int n = arr.length;
    System.out.println(distribution(arr, n));
}
}
 
// This code is contributed by ankita_saini

# Python 3 program to equally divide n
# elements into two sets such that second
# set has maximum distinct elements.
 
def distribution(arr, n):
    arr.sort(reverse = False)
    count = 1
    for i in range(1, n, 1):
        if (arr[i] > arr[i - 1]):
            count += 1
     
    return min(count, n / 2)
 
# Driver code
if __name__ == '__main__':
    arr = [1, 1, 2, 1, 3, 4]
    n = len(arr)
    print(int(distribution(arr, n)))
 
# This code is contributed by
# Shashank_Sharma

// C# program to equally divide
// n elements into two sets such
// that second set has maximum
// distinct elements.
using System;
 
class GFG
{
static int distribution(int []arr, int n)
{
    Array.Sort(arr);
    int count = 1;
    for (int i = 1; i < n; i++)
        if (arr[i] > arr[i - 1])
            count++;
     
    return Math.Min(count, n / 2);
}
 
// Driver code
public static void Main(String []args)
{
    int []arr= { 1, 1, 2, 1, 3, 4 };
    int n = arr.Length;
    Console.WriteLine(distribution(arr, n));
}
}
 
// This code is contributed
// by ankita_saini

<?php
// PHP program to equally divide n elements
// into two sets such that second set has
// maximum distinct elements.
 
function distribution($arr, $n)
{
    sort($arr);
    $count = 1;
    for ($i = 1; $i <$n; $i++)
        if ($arr[$i] > $arr[$i - 1])
            $count++;
     
    return min($count, $n / 2);
}
 
// Driver code
$arr = array(1, 1, 2, 1, 3, 4 );
$n = count($arr);
echo(distribution($arr, $n));
 
// This code is contributed
// by inder_verma
?>

<script>
 
// Javascript program to equally divide n elements
// into two sets such that second set has
// maximum distinct elements.
 
function distribution(arr, n)
{
    arr.sort((a,b)=>a-b);
    var count = 1;
    for (var i = 1; i < n; i++)
        if (arr[i] > arr[i - 1])
            count++;
     
    return Math.min(count, parseInt(n / 2));
}
 
// Driver code
var arr = [1, 1, 2, 1, 3, 4];
var n = arr.length;
document.write( distribution(arr, n));
 
</script>

Producción: 

3

Complejidad del tiempo: O(N log N)

Espacio Auxiliar: O(1)

Enfoque 2 (usando el conjunto hash) 
Otra forma de encontrar un elemento distinto es el conjunto, inserte todo el elemento en el conjunto. Por la propiedad de un conjunto, contendrá solo elementos únicos. Al final, podemos contar el número de elementos en el conjunto, dado por, digamos contar. El valor que se devolverá volverá a estar dado por min(count, n/2).

// C++ program to equally divide n elements
// into two sets such that second set has
// maximum distinct elements.
#include <bits/stdc++.h>
using namespace std;
 
int distribution(int arr[], int n)
{
    set<int, greater<int> > resources;
 
    // Insert all the resources in the set
    // There will be unique resources in the set
    for (int i = 0; i < n; i++)
        resources.insert(arr[i]);   
 
    // return minimum of distinct resources
    // and n/2
      int m = resources.size();
    return min(m, n / 2);
}
 
// Driver code
int main()
{
    int arr[] = { 1, 1, 2, 1, 3, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << distribution(arr, n) << endl;
    return 0;
}

// Java program to equally divide n elements
// into two sets such that second set has
// maximum distinct elements.
import java.util.*;
 
class GFG
{
 
static int distribution(int arr[], int n)
{
    Set<Integer> resources = new HashSet<Integer>();
 
    // Insert all the resources in the set
    // There will be unique resources in the set
    for (int i = 0; i < n; i++)
        resources.add(arr[i]);
 
    // return minimum of distinct resources
    // and n/2
    return Math.min(resources.size(), n / 2);
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 1, 1, 2, 1, 3, 4 };
    int n = arr.length;
    System.out.print(distribution(arr, n) +"\n");
}
}
 
// This code is contributed by Rajput-Ji

# Python3 program to equally divide n elements
# into two sets such that second set has
# maximum distinct elements.
def distribution(arr, n):
    resources = set()
     
    # Insert all the resources in the set
    # There will be unique resources in the set
    for i in range(n):
        resources.add(arr[i]);
 
        # return minimum of distinct resources
        # and n/2
    return min(len(resources), n // 2);
 
# Driver code
if __name__ == '__main__':
    arr = [ 1, 1, 2, 1, 3, 4 ];
    n = len(arr);
    print(distribution(arr, n), "");
     
# This code is contributed by PrinciRaj1992

// C# program to equally divide n elements
// into two sets such that second set has
// maximum distinct elements.
using System;
using System.Collections.Generic;
 
class GFG
{
 
static int distribution(int []arr, int n)
{
    HashSet<int> resources = new HashSet<int>();
 
    // Insert all the resources in the set
    // There will be unique resources in the set
    for (int i = 0; i < n; i++)
        resources.Add(arr[i]);
 
    // return minimum of distinct resources
    // and n/2
    return Math.Min(resources.Count, n / 2);
}
 
// Driver code
public static void Main(String[] args)
{
    int []arr = { 1, 1, 2, 1, 3, 4 };
    int n = arr.Length;
    Console.Write(distribution(arr, n) +"\n");
}
}
 
// This code is contributed by PrinciRaj1992

<script>
    // Javascript program to equally divide n elements
    // into two sets such that second set has
    // maximum distinct elements.
    function distribution(arr, n)
    {
        let resources = new Set();
 
        // Insert all the resources in the set
        // There will be unique resources in the set
        for (let i = 0; i < n; i++)
            resources.add(arr[i]);
 
        // return minimum of distinct resources
        // and n/2
        return Math.min(resources.size, parseInt(n / 2, 10));
    }
     
    let arr = [ 1, 1, 2, 1, 3, 4 ];
    let n = arr.length;
    document.write(distribution(arr, n) +"</br>");
 
// This code is contributed by mukesh07.
</script>

3

Complejidad de tiempo: O(nlogn), donde n es el tamaño de la array dada
Espacio auxiliar: O(n), ya que el espacio adicional de tamaño n se usa para crear un conjunto