1481. Least Number of Unique Integers after K Removals

public class Solution {
    public int FindLeastNumOfUniqueInts(int[] arr, int k) {
        var freqMap = new Dictionary<int, int>();
        foreach (var num in arr) {
            if (freqMap.ContainsKey(num)) {
                freqMap[num]++;
            } else {
                freqMap[num] = 1;
            }
        }
        
        var frequencies = new List<int>(freqMap.Values);
        frequencies.Sort();
        
        int elementsRemoved = 0;
        for (int i = 0; i < frequencies.Count; i++) {
            elementsRemoved += frequencies[i];
            if (elementsRemoved > k) {
                return frequencies.Count - i;
            }
        }
        
        return 0;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int FindLeastNumOfUniqueInts(vector<int>& arr, int k) {
        var freqMap = new unordered_map<int, int>();
        foreach (var num in arr) {
            if (freqMap.count(num)) {
                freqMap[num]++;
            } else {
                freqMap[num] = 1;
            }
        }
        
        var frequencies = new List<int>(freqMap.Values);
        frequencies.Sort();
        
        int elementsRemoved = 0;
        for (int i = 0; i < frequencies.size(); i++) {
            elementsRemoved += frequencies[i];
            if (elementsRemoved > k) {
                return frequencies.size() - i;
            }
        }
        
        return 0;
    }
}

import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
    public int FindLeastNumOfUniqueInts(int[] arr, int k) {
        var freqMap = new HashMap<int, int>();
        foreach (var num in arr) {
            if (freqMap.containsKey(num)) {
                freqMap[num]++;
            } else {
                freqMap[num] = 1;
            }
        }
        
        var frequencies = new List<int>(freqMap.Values);
        frequencies.Sort();
        
        int elementsRemoved = 0;
        for (int i = 0; i < frequencies.size(); i++) {
            elementsRemoved += frequencies[i];
            if (elementsRemoved > k) {
                return frequencies.size() - i;
            }
        }
        
        return 0;
    }
}

var findLeastNumOfUniqueInts = function(arr, k) {
    let freqMap = new Map();
    for (let num of arr) {
        freqMap.set(num, (freqMap.get(num) || 0) + 1);
    }
    
    let frequencies = Array.from(freqMap.values());
    frequencies.sort((a, b) => a - b);
    
    let elementsRemoved = 0;
    for (let i = 0; i < frequencies.length; i++) {
        elementsRemoved += frequencies[i];
        if (elementsRemoved > k) {
            return frequencies.length - i;
        }
    }
    
    return 0;
};

class Solution:
    def findLeastNumOfUniqueInts(self, arr, k):
        from collections import Counter
        freq_map = Counter(arr)
        frequencies = sorted(freq_map.values())
        
        elements_removed = 0
        for i, freq in enumerate(frequencies):
            elements_removed += freq
            if elements_removed > k:
                return len(frequencies) - i
        
        return 0

import "sort"

func findLeastNumOfUniqueInts(arr []int, k int) int {
    freqMap := make(map[int]int)
    for _, num := range arr {
        freqMap[num]++
    }
    
    frequencies := make([]int, 0, len(freqMap))
    for _, freq := range freqMap {
        frequencies = append(frequencies, freq)
    }
    
    sort.Ints(frequencies)
    
    elementsRemoved := 0
    for i, freq := range frequencies {
        elementsRemoved += freq
        if elementsRemoved > k {
            return len(frequencies) - i
        }
    }
    
    return 0
}

Algorithm

Инициализация и построение частотного arrayа:

Создайте хеш-таблицу для отслеживания частот elementов arrayа arr.

Итеративно увеличивайте частоту elementов в хеш-таблице.

Сортировка и удаление elementов:

Создайте array частот и заполните его значениями из хеш-таблицы.

Отсортируйте array частот.

Инициализируйте переменную для отслеживания числа удаленных elementов и итеративно добавляйте частоты, пока количество удаленных elementов не превысит k.

Возвращение результата:

Если количество удаленных elementов превысило k, return оставшееся количество уникальных elementов.

Если все elementы были удалены, return 0.

😎