Número mínimo de elementos distintos después de eliminar m elementos

Dada una array de elementos, un elemento de índice i-th denota la identificación del elemento, y dado un número m, la tarea es eliminar m elementos de modo que quede un mínimo de identificación distinta. Imprime el número de identificaciones distintas.

Ejemplos: 

Input : arr[] = { 2, 2, 1, 3, 3, 3} 
            m = 3
Output : 1
Remove 1 and both 2's.So, only 3 will be 
left that's why distinct id is 1.

Input : arr[] = { 2, 4, 1, 5, 3, 5, 1, 3} 
            m = 2
Output : 3
Remove 2 and 4 completely. So, remaining ids 
are 1, 3 and 5 i.e. 3

Preguntado en: Morgan Stanl

1. Cuente la aparición de elementos y guárdelos en el hash. 
2. Ordenar el hachís. 
3. Comience a eliminar elementos del hash cuyo conteo de frecuencia sea menor que m. 
4. Devuelve el número de valores que quedan en el hash.

Implementación:

// C++ program for above implementation
#include <bits/stdc++.h>
using namespace std;
 
// Function to find distinct id's
int distinctIds(int arr[], int n, int mi)
{
    unordered_map<int, int> m;
    vector<pair<int, int> > v;
    int count = 0;
 
    // Store the occurrence of ids
    for (int i = 0; i < n; i++)
        m[arr[i]]++;
 
    // Store into the vector second as first and vice-versa
    for (auto it = m.begin(); it != m.end(); it++)
        v.push_back(make_pair(it->second, it->first));
 
    // Sort the vector
    sort(v.begin(), v.end());
 
    int size = v.size();
 
    // Start removing elements from the beginning
    for (int i = 0; i < size; i++) {
 
        // Remove if current value is less than
        // or equal to mi
        if (v[i].first <= mi) {
            mi -= v[i].first;
            count++;
        }
 
        // Return the remaining size
        else
            return size - count;
    }
    return size - count;
}
 
// Driver code
int main()
{
    int arr[] = { 2, 3, 1, 2, 3, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    int m = 3;
 
    cout << distinctIds(arr, n, m);
    return 0;
}

import java.util.*;
 
class Solution {
    static int distinctIds(int arr[], int n, int m)
    {
        // Creating HashMap to store frequency count
        HashMap<Integer, Integer> h = new HashMap<>();
 
        for (int i = 0; i < n; i++) {
            if (h.containsKey(arr[i])) {
                h.put(arr[i], h.get(arr[i]) + 1);
            }
            else {
                h.put(arr[i], 1);
            }
        }
 
        // Creating a list to sort HashMap according to
        // values
        List<Map.Entry<Integer, Integer> > l
            = new LinkedList<Map.Entry<Integer, Integer> >(
                h.entrySet());
 
        // sorting using Comparator
        Collections.sort(
            l,
            new Comparator<Map.Entry<Integer, Integer> >() {
                public int compare(
                    Map.Entry<Integer, Integer> o1,
                    Map.Entry<Integer, Integer> o2)
                {
                    return o1.getValue() - o2.getValue();
                }
            });
 
        // Creating new map after sorting and also
        // maintaining insertion order
        LinkedHashMap<Integer, Integer> lh
            = new LinkedHashMap<>();
        for (Map.Entry<Integer, Integer> e : l) {
            lh.put(e.getKey(), e.getValue());
        }
 
        for (Integer i : lh.keySet()) {
            // removing element from whose frequency count is
            // less than m ,Sorted manner to get minimum
            // distinct ids
            if (h.get(i) <= m) {
                m -= h.get(i);
                h.remove(i);
            }
        }
 
        return h.size();
    }
 
    public static void main(String[] args)
    {
        // TODO Auto-generated method stub
        int arr[] = { 2, 4, 1, 5, 3, 5, 1, 3 };
        int m = 2;
 
        System.out.println(distinctIds(arr, arr.length, m));
    }
}

# Python program for above implementation
 
# Function to find distinct id's
def distinctIds(arr, n, mi):
  m = {}
  v = []
  count = 0
 
  # Store the occurrence of ids
  for i in range(n):
    if arr[i] in m:
      m[arr[i]] += 1
    else:
      m[arr[i]] = 1
 
  # Store into the list value as key and vice-versa
  for i in m:
    v.append([m[i],i])
 
  v.sort()
  size = len(v)
 
  # Start removing elements from the beginning
  for i in range(size):
     
    # Remove if current value is less than
    # or equal to mi
    if (v[i][0] <= mi):
      mi -= v[i][0]
      count += 1
         
    else:   # Return the remaining size
      return size - count
  return size - count
 
# Driver code
arr = [ 2, 3, 1, 2, 3, 3 ]
n = len(arr)
 
m = 3
 
# To display the result
print(distinctIds(arr, n, m))
 
# This code is contributed by rohitsingh07052

// C# program for Minimum number of
// distinct elements after removing m items
using System;
using System.Collections.Generic; 
class GFG
{
 
  // Function to find distinct id's
  static int distinctIds(int[] arr, int n, int mi)
  {
 
    Dictionary<int, int> m = new Dictionary<int, int>(); 
    int count = 0;
    int size = 0;
 
    // Store the occurrence of ids
    for (int i = 0; i < n; i++)
    {
 
      // If the key is not add it to map
      if (m.ContainsKey(arr[i]) == false)
      {
        m[arr[i]] = 1;
        size++;
      }
 
      // If it is present then increase the value by 1
      else
      {
        m[arr[i]]++;
      }
    }
 
    // Start removing elements from the beginning
    foreach(KeyValuePair<int, int> mp in m)
    {
 
      // Remove if current value is less than
      // or equal to mi
      if (mp.Key <= mi)
      {
        mi -= mp.Key;
        count++;
      }
    }
    return size - count;
  }
 
  // Driver code
  static void Main()
  {
 
    // TODO Auto-generated method stub
    int[] arr = {2, 3, 1, 2, 3, 3};
    int m = 3;
 
    Console.WriteLine(distinctIds(arr, arr.Length, m));
  }
}
 
// This code is contributed by divyeshrabadiya07

<script>
 
// Javascript program for above implementation
 
// Function to find distinct id's
function distinctIds(arr, n, mi)
{
    var m = new Map();
    var v = [];
    var count = 0;
 
    // Store the occurrence of ids
    for (var i = 0; i < n; i++)
    {
        if(m.has(arr[i]))
            m.set(arr[i], m.get(arr[i])+1)
        else
            m.set(arr[i], 1)
    }
 
    // Store into the vector second as first and vice-versa
    m.forEach((value, key) => {
         
        v.push([value, key]);
    });
 
    // Sort the vector
    v.sort()
 
    var size = v.length;
 
    // Start removing elements from the beginning
    for (var i = 0; i < size; i++) {
 
        // Remove if current value is less than
        // or equal to mi
        if (v[i][0] <= mi) {
            mi -= v[i][0];
            count++;
        }
 
        // Return the remaining size
        else
            return size - count;
    }
    return size - count;
}
 
// Driver code
var arr = [2, 3, 1, 2, 3, 3 ];
var n = arr.length;
var m = 3;
document.write( distinctIds(arr, n, m));
 
// This code is contributed by immportantly.
</script>

1

Complejidad de tiempo: O(n log n)

Este artículo es una contribución de Sahil Chhabra . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.