Máximo de elementos distintos después de eliminar k elementos

Dada una array arr[] que contiene n elementos. El problema es encontrar el número máximo de elementos distintos (no repetidos) después de eliminar k elementos de la array. 
Nota: 1 <= k <= n.
Ejemplos: 

Input : arr[] = {5, 7, 5, 5, 1, 2, 2}, k = 3
Output : 4
Remove 2 occurrences of element 5 and
1 occurrence of element 2.

Input : arr[] = {1, 2, 3, 4, 5, 6, 7}, k = 5
Output : 2

Input : arr[] = {1, 2, 2, 2}, k = 1
Output : 1

Enfoque: Los siguientes son los pasos: 

1. Haga un conjunto múltiple a partir de la array dada.

2. Durante la creación de este conjunto múltiple, verifique si el elemento actual está presente o no en el conjunto múltiple, si ya está presente, simplemente reduzca el valor k y no lo inserte en el conjunto múltiple.

3. Si k se convierte en 0, simplemente coloque los valores en multiset.

4. Después de recorrer toda la array dada, 

       a) si k no es igual a cero, significa que el conjunto múltiple consta solo de elementos únicos y tenemos que eliminar cualquiera de los k elementos del conjunto múltiple para hacer k = 0, por lo que en este caso la respuesta será el tamaño del conjunto múltiple menos el valor de k en ese momento.

        b) si k es igual a cero, significa que puede haber valores duplicados presentes en el conjunto múltiple, así que coloque todos los valores en un conjunto y el tamaño de este conjunto será el número de elementos distintos después de eliminar k elementos

// CPP implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
   
// function to find maximum distinct elements
// after removing k elements
int maxDistinctNum(int a[], int n, int k)
{
  int i;
  multiset<int> s;
  // making multiset from given array
        for(i=0;i<n;i++){
            if(s.find(a[i])==s.end()||k==0)
            s.insert(a[i]);
            else
            {
                k--;
            }
        }
   
        if(k!=0)
        return s.size()-k;
        else{
            set<int> st;
            for(auto it:s){
                st.insert(it);
            }
            return st.size();
        }
}
 
// Driver Code
int main()
{
    int arr[] = { 5, 7, 5, 5, 1, 2, 2 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
   
    // Function Call
    cout << "Maximum distinct elements = "
         << maxDistinctNum(arr, n, k);
    return 0;
}

// Java implementation of the
// above approach
import java.util.*;
class GFG{
     
// Function to find maximum
// distinct elements after
// removing k elements
static int maxDistinctNum(int arr[],
                          int n, int k)
{
  HashMap<Integer,
          Integer> numToFreq = new HashMap<>();
 
  // Build frequency map
  for(int i = 0 ; i < n ; i++)
  {
    numToFreq.put(arr[i],
    numToFreq.getOrDefault(arr[i], 0) + 1);
  }
 
  int result = 0;
 
  // Min-heap
  PriorityQueue<Integer> minHeap =
                new PriorityQueue<Integer>();
 
  // Add all number with freq=1 to
  // result and push others to minHeap
  for(Map.Entry<Integer,
                Integer> p : numToFreq.entrySet())
  {
    if(p.getValue() == 1)
      ++result;
    else
      minHeap.add(p.getValue());
  }
 
  // Perform k operations
  while(k != 0 && !minHeap.isEmpty())
  {
    // Pop the top() element
    Integer t = minHeap.poll();
     
    // Increment Result
    if(t == 1)
    {
      ++result;
    }
 
    // Reduce t and k
    // Push it again
    else
    {
      --t;
      --k;
      minHeap.add(t);
    }
  }
 
  // Return result
  return result;
}
 
// Driver code
public static void main(String[] args)
{       
  int arr[] = {5, 7, 5, 5, 1, 2, 2};
  int n = arr.length;
  int k = 3;
 
  // Function Call
  System.out.println("Maximum distinct elements = " + 
                      maxDistinctNum(arr, n, k));
}
}
 
// This code is contributed by rutvik_56

<script>
 
// Javascript implementation of the above approach
   
// function to find maximum distinct elements
// after removing k elements
function maxDistinctNum(a, n, k)
{
  var i;
  var s = [];
  // making multiset from given array
        for(i=0;i<n;i++){
            if(!s.includes(a[i])||k==0)
            s.push(a[i]);
            else
            {
                k--;
            }
        }
   
        if(k!=0)
            return s.size-k;
        else{
            var st = new Set();
            s.forEach(element => {
                st.add(element);
            });
             
            return st.size;
        }
}
 
// Driver Code
var arr = [5, 7, 5, 5, 1, 2, 2];
var n = arr.length;
var k = 3;
 
// Function Call
document.write( "Maximum distinct elements = "
      +  maxDistinctNum(arr, n, k));
 
// This code is contributed by itsok.
</script>

Maximum distinct elements = 4

Producción: 
 

Maximum distinct elements = 4

Complejidad de tiempo: O(k*logd), donde d es el número de elementos distintos en la array dada.

Otro enfoque: siga los pasos a continuación para resolver este problema:

• Encuentra el número de juguetes distintos.
• Suma del número de elementos excepto un elemento de todos los juguetes distintos.
• Verifique la suma si es mayor o igual a K y luego devuelva todos los elementos distintos.
• De lo contrario, disminuya el número de elementos distintos y complete K.
• Tamaño de retorno del vector.

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

// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
// function to return maximum number of distinct Toys
int MaxNumber(int arr[], int N, int K)
{
    // Count Number of distinct Number
    unordered_map<int, int> mp;
    for (int i = 0; i < N; i++) {
        mp[arr[i]]++;
    }
    // push them into vector
    vector<int> v1;
    for (auto i : mp) {
        v1.push_back(i.second);
    }
    // add number of element except one element from every
    // distinct element
    int temp = 0;
    for (int i = 0; i < v1.size(); i++) {
        temp += v1[i] - 1;
    }
    // check if it is greater than simply return size of
    // vector otherwise decrement size of vector to fill k
    if (K <= temp) {
        return v1.size();
    }
    else {
        K = K - temp;
        int ans = v1.size();
        while (K) {
            ans--;
            K--;
        }
        return ans;
    }
}
// Driver Code
int main()
{
    // array
    int arr[] = { 10, 10, 10, 50, 50 };
    int K = 3;
    // size of array
    int N = sizeof(arr) / sizeof(arr[0]);
    cout << MaxNumber(arr, N, K) << endl;
    return 0;
}

# Python3 code for the above approach
 
# function to return maximum number of distinct Toys
def MaxNumber(arr, N, K):
   
    # Count Number of distinct Number
    mp = {}
    for i in range(N):
        if arr[i] not in mp:
            mp[arr[i]] = 0
        mp[arr[i]] += 1
         
        # push them into vector
    v1 = []
    for i in mp:
        v1.append(mp[i])
 
     # add number of element except one element from every
    # distinct element
    temp = 0
    for i in range(len(v1)):
        temp += v1[i]-1
         
     # check if it is greater than simply return size of
    # vector otherwise decrement size of vector to fill k
    if K <= temp:
        return len(v1)
    else:
        K = K-temp
        ans = len(v1)
        while K:
            ans -= 1
            K -= 1
        return ans
 
# Driver Code
if __name__ == "__main__":
   
  # Array
    arr = [10, 10, 10, 50, 50]
    K = 3
     
    # Size of array
    N = len(arr)
    print(MaxNumber(arr, N, K))
 
    # This code is contributed by vivekmaddheshiya205

2

Complejidad de tiempo: O(N)

Complejidad espacial: O(N)