Particione una array en dos subconjuntos con el mismo número de elementos únicos

Dada una array arr[] que consta de N enteros, la tarea es dividir la array en dos subconjuntos de modo que el recuento de elementos únicos en ambos subconjuntos sea el mismo y para cada elemento, imprima 1 si ese elemento pertenece al primer subconjunto . De lo contrario, imprima 2 . Si no es posible hacer tal partición, imprima «-1» .

Ejemplos:

Entrada: arr[] = {1, 1, 2, 3, 4, 4}
Salida: 1 1 1 2 1 1
Explicación: Considere el primer y segundo subconjunto de la partición de la array como {1, 1, 2, 4 4} y {3}. Ahora, la partición de subconjuntos anterior tiene la misma cantidad de elementos distintos.

Entrada: arr[] = {1, 1, 2, 2, 3}
Salida: -1

Enfoque ingenuo: el problema dado se puede resolver generando todas las particiones posibles de los elementos de la array en dos subconjuntos y, si existe alguna partición cuyo recuento de elementos distintos sea el mismo, imprima 1 y 2 de acuerdo con el conjunto respectivo de los elementos de la array . a. De lo contrario, imprima «-1» ya que no existe ninguna partición posible de la array.

Complejidad temporal: O(N*2 N )
Espacio auxiliar: O(N)

Enfoque eficiente: el enfoque anterior también se puede optimizar encontrando la frecuencia de elementos de array únicos si la frecuencia es impar, entonces no existe tal partición posible. De lo contrario, imprima la partición del subconjunto en consecuencia. Siga los pasos a continuación para resolver el problema:

  • Inicialice un mapa , diga M para almacenar la frecuencia de todos los elementos de la array .
  • Inicialice la array, digamos ans[] que almacena el número de subconjunto al que pertenece cada elemento de la array.
  • Encuentre el conteo de los elementos únicos en la array contando el elemento que tiene la frecuencia 1 en el mapa M . Sea esta cuenta C .
  • Si el valor de C es par , mueva la mitad de estos elementos al primer subconjunto marcando esos elementos como 1 y reste todos los elementos como 2 en la array ans[] .
  • De lo contrario, verifique si existe algún elemento que tenga una frecuencia mayor que 2 , luego cambie una instancia de ese elemento al segundo subconjunto. De lo contrario, imprima «-1» .

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 partition the array into
// two subsets such that count of unique
// elements in both subsets is the same
void arrayPartition(int a[], int n)
{
    // Stores the subset number for
    // each array elements
    int ans[n];
 
    // Stores the count of unique
    // array elements
    int cnt = 0;
    int ind, flag = 0;
 
    // Stores the frequency of elements
    map<int, int> mp;
 
    // Traverse the array
    for (int i = 0; i < n; i++) {
        mp[a[i]]++;
    }
 
    // Count of elements having a
    // frequency of 1
    for (int i = 0; i < n; i++) {
 
        if (mp[a[i]] == 1)
            cnt++;
 
        // Check if there exists any
        // element with frequency > 2
        if (mp[a[i]] > 2 && flag == 0) {
            flag = 1;
            ind = i;
        }
    }
 
    // Count of elements needed to
    // have frequency exactly 1 in
    // each subset
    int p = (cnt + 1) / 2;
    int ans1 = 0;
 
    // Initialize all values in the
    /// array ans[] as 1
    for (int i = 0; i < n; i++)
        ans[i] = 1;
 
    // Traverse the array ans[]
    for (int i = 0; i < n; i++) {
 
        // This array element is a
        // part of first subset
        if (mp[a[i]] == 1 && ans1 < p) {
            ans[i] = 1;
            ans1++;
        }
 
        // Half array elements with
        // frequency 1 are part of
        // the second subset
        else if (mp[a[i]] == 1) {
            ans[i] = 2;
        }
    }
 
    // If count of elements is exactly
    // 1 are odd and has no element
    // with frequency > 2
    if (cnt % 2 == 1 && flag == 0) {
        cout << -1 << endl;
        return;
    }
 
    // If count of elements that occurs
    // exactly once are even
    if (cnt % 2 == 0) {
 
        // Print the result
        for (int i = 0; i < n; i++) {
            cout << ans[i] << " ";
        }
    }
 
    // If the count of elements has
    // exactly 1 frequency are odd
    // and there is an element with
    // frequency greater than 2
    else {
 
        // Print the result
        for (int i = 0; i < n; i++) {
            if (ind == i)
                cout << 2 << " ";
            else
                cout << ans[i] << " ";
        }
    }
}
 
// Driver Codea
int main()
{
    int arr[] = { 1, 1, 2, 3, 4, 4 };
    int N = sizeof(arr) / sizeof(arr[0]);
    arrayPartition(arr, N);
 
    return 0;
}

Java

// Java program for the above approach
 
import java.util.HashMap;
 
 
 
class GFG{
 
// Function to partition the array into
// two subsets such that count of unique
// elements in both subsets is the same
public static void arrayPartition(int a[], int n)
{
    // Stores the subset number for
    // each array elements
    int[] ans = new int[n];
 
    // Stores the count of unique
    // array elements
    int cnt = 0;
    int ind = 0, flag = 0;
 
    // Stores the frequency of elements
    HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>();
 
    // Traverse the array
    for (int i = 0; i < n; i++) {
        if(mp.containsKey(a[i])){
            mp.put(a[i], mp.get(a[i]) + 1);
        }else{
            mp.put(a[i], 1);
        }
    }
 
    // Count of elements having a
    // frequency of 1
    for (int i = 0; i < n; i++) {
 
        if (mp.get(a[i]) == 1)
            cnt++;
 
        // Check if there exists any
        // element with frequency > 2
        if (mp.get(a[i]) > 2 && flag == 0) {
            flag = 1;
            ind = i;
        }
    }
 
    // Count of elements needed to
    // have frequency exactly 1 in
    // each subset
    int p = (cnt + 1) / 2;
    int ans1 = 0;
 
    // Initialize all values in the
    /// array ans[] as 1
    for (int i = 0; i < n; i++)
        ans[i] = 1;
 
    // Traverse the array ans[]
    for (int i = 0; i < n; i++) {
 
        // This array element is a
        // part of first subset
        if (mp.get(a[i]) == 1 && ans1 < p) {
            ans[i] = 1;
            ans1++;
        }
 
        // Half array elements with
        // frequency 1 are part of
        // the second subset
        else if (mp.get(a[i]) == 1) {
            ans[i] = 2;
        }
    }
 
    // If count of elements is exactly
    // 1 are odd and has no element
    // with frequency > 2
    if (cnt % 2 == 1 && flag == 0) {
        System.out.println(-1 + "\n");
        return;
    }
 
    // If count of elements that occurs
    // exactly once are even
    if (cnt % 2 == 0) {
 
        // Print the result
        for (int i = 0; i < n; i++) {
            System.out.print(ans[i] + " ");
        }
    }
 
    // If the count of elements has
    // exactly 1 frequency are odd
    // and there is an element with
    // frequency greater than 2
    else {
 
        // Print the result
        for (int i = 0; i < n; i++) {
            if (ind == i)
            System.out.print(2 + " ");
            else
            System.out.print(ans[i] + " ");
        }
    }
}
 
// Driver Codea
public static void main(String args[])
{
    int arr[] = { 1, 1, 2, 3, 4, 4 };
    int N = arr.length;
    arrayPartition(arr, N);
 
}
}
 
// This code is contributed by gfgking.

Python3

# Python3 program for the above approach
 
# Function to partition the array into
# two subsets such that count of unique
# elements in both subsets is the same
def arrayPartition(a, n):
     
    # Stores the subset number for
    # each array elements
    ans = [0] * n
 
    # Stores the count of unique
    # array elements
    cnt = 0
    ind, flag = 0, 0
 
    # Stores the frequency of elements
    mp = {}
 
    # Traverse the array
    for i in a:
        mp[i] = mp.get(i, 0) + 1
 
    # Count of elements having a
    # frequency of 1
    for i in range(n):
        if ((a[i] in mp) and mp[a[i]] == 1):
            cnt += 1
 
        # Check if there exists any
        # element with frequency > 2
        if (mp[a[i]] > 2 and flag == 0):
            flag = 1
            ind = i
 
    # Count of elements needed to
    # have frequency exactly 1 in
    # each subset
    p = (cnt + 1) // 2
    ans1 = 0
 
    # Initialize all values in the
    # array ans[] as 1
    for i in range(n):
        ans[i] = 1
 
    # Traverse the array ans[]
    for i in range(n):
         
        # This array element is a
        # part of first subset
        if ((a[i] in mp) and mp[a[i]] == 1 and
            ans1 < p):
            ans[i] = 1
            ans1 += 1
 
        # Half array elements with
        # frequency 1 are part of
        # the second subset
        elif ((a[i] in mp) and mp[a[i]] == 1):
            ans[i] = 2
 
    # If count of elements is exactly
    # 1 are odd and has no element
    # with frequency > 2
    if (cnt % 2 == 1 and flag == 0):
        print (-1)
        return
 
    # If count of elements that occurs
    # exactly once are even
    if (cnt % 2 == 0):
 
        # Print the result
        print(*ans)
 
    # If the count of elements has
    # exactly 1 frequency are odd
    # and there is an element with
    # frequency greater than 2
    else:
         
        # Print the result
        for i in range(n):
            if (ind == i):
                print(2, end = " ")
            else:
                print(ans[i], end = " ")
 
# Driver Codea
if __name__ == '__main__':
     
    arr = [ 1, 1, 2, 3, 4, 4 ]
    N = len(arr)
     
    arrayPartition(arr, N)
 
# This code is contributed by mohit kumar 29

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to partition the array into
// two subsets such that count of unique
// elements in both subsets is the same
static void arrayPartition(int []a, int n)
{
    // Stores the subset number for
    // each array elements
    int []ans = new int[n];
 
    // Stores the count of unique
    // array elements
    int cnt = 0;
    int ind=0, flag = 0;
 
    // Stores the frequency of elements
    Dictionary<int,int> mp = new Dictionary<int,int>();
 
    // Traverse the array
    for (int i = 0; i < n; i++) {
        if(mp.ContainsKey(a[i]))
         mp[a[i]]++;
        else
          mp.Add(a[i],1);
    }
 
    // Count of elements having a
    // frequency of 1
    for (int i = 0; i < n; i++) {
 
        if (mp.ContainsKey(a[i]) && mp[a[i]] == 1)
            cnt++;
 
        // Check if there exists any
        // element with frequency > 2
        if (mp.ContainsKey(a[i]) && mp[a[i]] > 2 && flag == 0) {
            flag = 1;
            ind = i;
        }
    }
 
    // Count of elements needed to
    // have frequency exactly 1 in
    // each subset
    int p = (cnt + 1) / 2;
    int ans1 = 0;
 
    // Initialize all values in the
    /// array ans[] as 1
    for (int i = 0; i < n; i++)
        ans[i] = 1;
 
    // Traverse the array ans[]
    for (int i = 0; i < n; i++) {
 
        // This array element is a
        // part of first subset
        if (mp.ContainsKey(a[i]) && mp[a[i]] == 1 && ans1 < p) {
            ans[i] = 1;
            ans1++;
        }
 
        // Half array elements with
        // frequency 1 are part of
        // the second subset
        else if (mp.ContainsKey(a[i]) && mp[a[i]] == 1) {
            ans[i] = 2;
        }
    }
 
    // If count of elements is exactly
    // 1 are odd and has no element
    // with frequency > 2
    if (cnt % 2 == 1 && flag == 0) {
        Console.Write(-1);
        return;
    }
 
    // If count of elements that occurs
    // exactly once are even
    if (cnt % 2 == 0) {
 
        // Print the result
        for (int i = 0; i < n; i++) {
            Console.Write(ans[i] + " ");
        }
    }
 
    // If the count of elements has
    // exactly 1 frequency are odd
    // and there is an element with
    // frequency greater than 2
    else {
 
        // Print the result
        for (int i = 0; i < n; i++) {
            if (ind == i)
                Console.Write(2 + " ");
            else
                Console.Write(ans[i] + " ");
        }
    }
}
 
// Driver Codea
public static void Main()
{
    int []arr = { 1, 1, 2, 3, 4, 4 };
    int N = arr.Length;
    arrayPartition(arr, N);
}
}
 
// This code is contributed by SURENDRA_GANGWAR.

Javascript

<script>
 
// JavaScript program for the above approach
 
// Function to partition the array into
// two subsets such that count of unique
// elements in both subsets is the same
function arrayPartition(a, n) {
    // Stores the subset number for
    // each array elements
    let ans = new Array(n);
 
    // Stores the count of unique
    // array elements
    let cnt = 0;
    let ind, flag = 0;
 
    // Stores the frequency of elements
    let mp = new Map();
 
    // Traverse the array
    for (let i = 0; i < n; i++) {
        if (mp.has(a[i])) {
            mp.set(a[i], mp.get(a[i]) + 1)
        } else {
            mp.set(a[i], 1)
        }
    }
 
    // Count of elements having a
    // frequency of 1
    for (let i = 0; i < n; i++) {
 
        if (mp.get(a[i]) == 1)
            cnt++;
 
        // Check if there exists any
        // element with frequency > 2
        if (mp.get(a[i]) > 2 && flag == 0) {
            flag = 1;
            ind = i;
        }
    }
 
    // Count of elements needed to
    // have frequency exactly 1 in
    // each subset
    let p = Math.floor((cnt + 1) / 2);
    let ans1 = 0;
 
    // Initialize all values in the
    /// array ans[] as 1
    for (let i = 0; i < n; i++)
        ans[i] = 1;
 
    // Traverse the array ans[]
    for (let i = 0; i < n; i++) {
 
        // This array element is a
        // part of first subset
        if (mp.get(a[i]) == 1 && ans1 < p) {
            ans[i] = 1;
            ans1++;
        }
 
        // Half array elements with
        // frequency 1 are part of
        // the second subset
        else if (mp.get(a[i]) == 1) {
            ans[i] = 2;
        }
    }
 
    // If count of elements is exactly
    // 1 are odd and has no element
    // with frequency > 2
    if (cnt % 2 == 1 && flag == 0) {
        document.write(-1 + "<br>");
        return;
    }
 
    // If count of elements that occurs
    // exactly once are even
    if (cnt % 2 == 0) {
 
        // Print the result
        for (let i = 0; i < n; i++) {
            document.write(ans[i] + " ");
        }
    }
 
    // If the count of elements has
    // exactly 1 frequency are odd
    // and there is an element with
    // frequency greater than 2
    else {
 
        // Print the result
        for (let i = 0; i < n; i++) {
            if (ind == i)
                document.write(2 + " ");
            else
                document.write(ans[i] << " ");
        }
    }
}
 
// Driver Codea
 
let arr = [1, 1, 2, 3, 4, 4];
let N = arr.length
arrayPartition(arr, N);
 
</script>
Producción: 

1 1 1 2 1 1

 

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por ujjwalgoel1103 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *