Минимальное количество различных элементов после удаления m элементов


Сложный уровень средний
Часто спрашивают в BlackRock ByteDance Expedia Ола Кабс Oracle PayU SAP Labs Яндекс
массив дерево

Постановка задачи

Задача «Минимальное количество различных элементов после удаления m элементов» утверждает, что у вас есть массив и целое число m. Каждый элемент массива указывает идентификатор элемента. В постановке задачи предлагается удалить m элементов таким образом, чтобы осталось минимальное количество различных идентификаторов.

Пример

arr[] = {1, 3, 4, 2, 4, 1, 3 }

m=2
3

 

Минимальное количество различных элементов после удаления m элементов

arr[] = {1, 4, 4, 1}

m=2
2

Алгоритм поиска минимального количества различных элементов после удаления m элементов

1. Declare a map.
2. Set temp to 0.
3. Count and store the frequencies of each element of the array into the map and check how many unique keys are present in it and set it as a cap.
4. Traverse the map and check if the key element is less than or equal to m.
    1. If true then decrease the value of m up to that key and also increase the temp by 1.
    2. Else return cap-temp.
5. Return cap-temp

объяснение

Нам дано целое число массив. У нас есть постановка задачи, которая удаляет m элементов таким образом, чтобы после удаления. Итак, у нас должно быть минимальное количество идентификаторов различных элементов. Предположим, что у нас есть 4 числа, которые являются разными элементами, и если мы удалим два из них. У нас по-прежнему есть 2 разных элемента, но здесь дело обстоит иначе. Если у нас есть 4 разных числа, их может быть больше одного для каждого элемента. Затем мы можем удалить один и тот же элемент дважды или, может быть, два разных элемента, но мы должны минимизировать количество различных элементов после удаления m элементов.

Мы собираемся использовать Хеширования. Мы объявим Хэш-карта. Установив значения cap и temp равными 0, мы начнем обход массива, подсчет и сохранение частот каждого элемента массива в карту. Это потому, что нам нужно знать частоту каждого элемента. Но при обходе, если мы получим значение впервые, мы увеличим значение cap на 1, в основном, это работает для нас как емкость или размер.

Мы снова посетим все ключи и значения карты, на этот раз нам просто нужно определить, меньше ли какой-либо ключ карты m или равен m, затем уменьшим значение m на ключевые раз, нам нужно обновить m как м - ключ найдено и увеличьте значение темп. Если это условие не выполняется, нам просто нужно вернуть разницу между cap и temp. Наконец-то мы должны вернуть cap-temp, потому что это требуемый результат, если каждое условие удовлетворяется в if part, тогда мы должны добавить дополнительный оператор возврата.

Код:

Код C ++ для поиска минимального количества различных элементов после удаления m элементов

#include<iostream>
#include<unordered_map>
#include<vector>
#include<algorithm>

using namespace std;

int getMinimumDistinctIds(int arr[], int n, int m)
{
    unordered_map<int, int> MAP;
    vector<pair<int, int> > vec;
    int temp = 0;

    for (int i = 0; i < n; i++)
        MAP[arr[i]]++;

    for (auto it = MAP.begin(); it != MAP.end(); it++)
        vec.push_back(make_pair(it->second, it->first));

    sort(vec.begin(), vec.end());

    int cap = vec.size();

    for (int i = 0; i < cap; i++)
    {
        if (vec[i].first <= m)
        {
            m = m - vec[i].first;
            temp++;
        }
        else
            return cap - temp;
    }
    return cap - temp;
}
int main()
{
    int arr[] = { 1, 3, 4, 2, 4, 1, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int m = 2;
    cout << getMinimumDistinctIds(arr, n, m);
    return 0;
}
3

Код Java для поиска минимального количества различных элементов после удаления m элементов

import java.util.Map.Entry;
import java.util.Map;
import java.util.HashMap;


class MinimumDistinctId
{
    public static int getMinimumDistinctIds(int arr[], int n, int m)
    {
        Map<Integer, Integer> MAP = new HashMap<Integer, Integer>();
        int temp = 0;
        int cap = 0;
        for (int i = 0; i < n; i++)
        {
            if (MAP.containsKey(arr[i]) == false)
            {
                MAP.put(arr[i], 1);
                cap++;
            }
            else
                MAP.put(arr[i], MAP.get(arr[i]) + 1);
        }
        for (Entry<Integer, Integer> entry:MAP.entrySet())
        {
            if (entry.getKey() <= m)
            {
                m = m - entry.getKey();
                temp++;
            }
            else
                return cap - temp;
        }
        return cap - temp;
    }
    public static void main(String[] args)
    {
        int arr[] = {1, 3, 4, 2, 4, 1, 3};
        int m = 2;
        System.out.println(getMinimumDistinctIds(arr, arr.length, m));
    }
}
3

Анализ сложности

Сложность времени

O (N войти N), потому что мы использовали сортировку, которая отмечает верхнюю границу временной сложности.

Космическая сложность

НА), потому что мы использовали каждый элемент как ключ. У нас может быть почти N элементов.