1481. Least Number of Unique Integers after K Removals

leetcode medium

#array#csharp#hash-table#leetcode#medium#search#sort#two-pointers

Task

Дан массив целых чисел arr и целое число k. Найдите минимальное количество уникальных целых чисел после удаления ровно k элементов.

Пример:

Input: arr = [5,5,4], k = 1

Output: 1

Explanation: Remove the single 4, only 5 is left.

C# solution

matched/original

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;
    }
}

C++ solution

auto-draft, review before submit

#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;
    }
}

Java solution

auto-draft, review before submit

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;
    }
}

JavaScript solution

matched/original

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;
};

Python solution

matched/original

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

Go solution

matched/original

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
}

Explanation

Algorithm

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

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

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

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

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

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

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

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

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

Если все элементы были удалены, верните 0.

😎