Número mínimo de elementos distintos presentes en una subsecuencia de longitud K en una array

Dada una array A[] que consta de N enteros y un entero K , la tarea es contar el número mínimo de elementos distintos presentes en una subsecuencia de longitud K de la array dada, A .

Ejemplos:

Entrada: A = {3, 1, 3, 2, 3, 4, 5, 4}, K = 4
Salida: 2
Explicación: La subsecuencia de longitud 4 que contiene el número mínimo de elementos distintos es {3, 3, 3, 4 }, que consta de 2 elementos distintos, es decir, {3, 4}.

Entrada: A = {3, 1, 3, 2, 3, 4, 5, 4}, K = 5
Salida: 2
Explicación: La subsecuencia de longitud 5 que contiene el número mínimo de elementos distintos es {3, 3, 3, 4 , 4}, que consta de 2 elementos distintos, es decir, {3, 4}.

Enfoque ingenuo: el enfoque más simple es generar todas las subsecuencias de longitud K y, para cada subsecuencia, encontrar el número de elementos distintos presentes en ellas. Finalmente, imprima el número mínimo de elementos distintos presentes.

Complejidad de Tiempo: O(K * N ^K )
Espacio Auxiliar: O(N)

Enfoque eficiente: el enfoque anterior se puede optimizar utilizando Hashing . Siga los pasos a continuación para resolver el problema:

• Almacene las frecuencias de todos los elementos en la array dada, A[] en un HashMap , digamos M.
• Atraviese el hashmap , M y empuje las frecuencias en otra array, digamos V .
• Ordena la array V en orden decreciente .
• Inicialice dos variables, cnt y len como 0, para almacenar el resultado requerido y la longitud de la subsecuencia así formada.
• Recorre la array V[] usando una variable, digamos i
  • Si el valor de len ≥ K, entonces salga del bucle .
  • De lo contrario, incremente el valor de len en V[i] y cnt en 1 .
• Después de completar los pasos anteriores, imprima el valor de cnt como resultado.

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 to count the minimum number
// of distinct elements present in any
// subsequence of length K of the given array
void findMinimumDistinct(int A[], int N, int K)
{
 
    // Stores the frequency
    // of each array element
    unordered_map<int, int> mp;
 
    // Traverse the array
    for (int i = 0; i < N; i++)
 
        // Update frequency
        // of array elements
        mp[A[i]]++;
 
    // Store the required result
    int count = 0;
 
    // Store the length of the
    // required subsequence
    int len = 0;
 
    // Store the frequencies
    // in decreasing order
    vector<int> counts;
 
    // Traverse the map
    for (auto i : mp)
 
        // Push the frequencies
        // into the HashMap
        counts.push_back(i.second);
 
    // Sort the array in decreasing order
    sort(counts.begin(), counts.end(),
         greater<int>());
 
    // Add the elements into the subsequence
    // starting from one with highest frequency
    for (int i = 0; i < counts.size(); i++) {
 
        // If length of subsequence is >= k
        if (len >= K)
            break;
        len += counts[i];
        count++;
    }
 
    // Print the result
    cout << count;
}
 
// Driver Code
int main()
{
    int A[] = { 3, 1, 3, 2, 3, 4, 5, 4 };
    int K = 4;
 
    // Store the size of the array
    int N = sizeof(A) / sizeof(A[0]);
 
    // Function Call to count minimum
    // number of distinct elements
    // present in a K-length subsequence
    findMinimumDistinct(A, N, K);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to count the minimum number
// of distinct elements present in any
// subsequence of length K of the given array
static void findMinimumDistinct(int A[], int N, int K)
{
     
    // Stores the frequency
    // of each array element
    Map<Integer, Integer> mp = new HashMap<>();
 
    // Traverse the array
    for(int i = 0; i < N; i++)
     
        // Update frequency
        // of array elements
        mp.put(A[i], mp.getOrDefault(A[i], 0) + 1);
 
    // Store the required result
    int count = 0;
 
    // Store the length of the
    // required subsequence
    int len = 0;
 
    // Store the frequencies
    // in decreasing order
    ArrayList<Integer> counts = new ArrayList<>();
 
    // Traverse the map
    for(Map.Entry<Integer, Integer> i : mp.entrySet())
     
        // Push the frequencies
        // into the HashMap
        counts.add(i.getValue());
 
    // Sort the array in decreasing order
    Collections.sort(counts, (a, b) -> b - a);
 
    // Add the elements into the subsequence
    // starting from one with highest frequency
    for(int i = 0; i < counts.size(); i++)
    {
         
        // If length of subsequence is >= k
        if (len >= K)
            break;
             
        len += counts.get(i);
        count++;
    }
 
    // Print the result
    System.out.print(count);
}
 
// Driver code
public static void main(String[] args)
{
    int A[] = { 3, 1, 3, 2, 3, 4, 5, 4 };
    int K = 4;
 
    // Store the size of the array
    int N = A.length;
 
    // Function Call to count minimum
    // number of distinct elements
    // present in a K-length subsequence
    findMinimumDistinct(A, N, K);
}
}
 
// This code is contributed by offbeat

# Python3 program for the above approach
from collections import Counter
 
# Function to count the minimum number
# of distinct elements present in any
# subsequence of length K of the given array
def findMinimumDistinct(A, N, K):
     
    # Stores the frequency
    # of each array element
    mp = Counter(A)
     
    # Store the required result
    count = 0
     
    # Store the length of the
    # required subsequence
    length = 0
     
    # Store the frequencies
    # in decreasing order
    counts = []
     
    # Traverse the map
    for i in mp:
         
        # Push the frequencies
        # into the HashMap
        counts.append(mp[i])
         
    # Sort the array in decreasing order
    counts = sorted(counts)
    counts.reverse()
     
    # Add the elements into the subsequence
    # starting from one with highest frequency
    for i in range(len(counts)):
         
        # If length of subsequence is >= k
        if (length >= K):
            break
         
        length += counts[i]
        count += 1
         
    # Print the result
    print(count)
 
# Driver Code
A = [3, 1, 3, 2, 3, 4, 5, 4]
K = 4
 
# Store the size of the array
N = len(A)
 
# Function Call to count minimum
# number of distinct elements
# present in a K-length subsequence
findMinimumDistinct(A, N, K)
 
# This code is contributed by sudhanshugupta2019a

<script>
 
// JavaScript program for the above approach
 
 
// Function to count the minimum number
// of distinct elements present in any
// subsequence of length K of the given array
function findMinimumDistinct(A, N, K)
{
 
    // Stores the frequency
    // of each array element
    let mp = new Map();
 
    // Traverse the array
    for (let i = 0; i < N; i++){
 
        // Update frequency
        // of array elements
        if(mp.has(A[i])){
            mp.set(A[i],mp.get(A[i])+1)
        }
        else mp.set(A[i],1)
    }
 
    // Store the required result
    let count = 0;
 
    // Store the length of the
    // required subsequence
    let len = 0;
 
    // Store the frequencies
    // in decreasing order
    let counts = [];
 
    // Traverse the map
    for (let [i,j] of mp)
 
        // Push the frequencies
        // into the HashMap
        counts.push(j);
 
    // Sort the array in decreasing order
    counts.sort((a,b)=>b-a);
 
    // Add the elements into the subsequence
    // starting from one with highest frequency
    for (let i = 0; i < counts.length; i++) {
 
        // If length of subsequence is >= k
        if (len >= K)
            break;
        len += counts[i];
        count++;
    }
 
    // Print the result
    document.write(count);
}
 
// Driver Code
 
let A = [ 3, 1, 3, 2, 3, 4, 5, 4 ];
let K = 4;
 
// Store the size of the array
let N = A.length;
 
// Function Call to count minimum
// number of distinct elements
// present in a K-length subsequence
findMinimumDistinct(A, N, K);
 
// This code is contributed by shinjanpatra
</script>

2

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