Задача: 1481. Least Number of Unique Integers after K Removals
Сложность: medium

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

Пример:

Input: arr = [5,5,4], k = 1
Output: 1
Explanation: Remove the single 4, only 5 is left.

👨‍💻 Алгоритм:

1⃣Инициализация и построение частотного массива:
Создайте хеш-таблицу для отслеживания частот элементов массива arr.
Итеративно увеличивайте частоту элементов в хеш-таблице.

2⃣Сортировка и удаление элементов:
Создайте массив частот и заполните его значениями из хеш-таблицы.
Отсортируйте массив частот.
Инициализируйте переменную для отслеживания числа удаленных элементов и итеративно добавляйте частоты, пока количество удаленных элементов не превысит k.

3⃣Возвращение результата:
Если количество удаленных элементов превысило k, верните оставшееся количество уникальных элементов.
Если все элементы были удалены, верните 0.

😎 Решение:

class Solution {
    func findLeastNumOfUniqueInts(_ arr: [Int], _ k: Int) -> Int {
        var freqMap = [Int: Int]()
        for num in arr {
            freqMap[num, default: 0] += 1
        }
        
        var frequencies = Array(freqMap.values)
        frequencies.sort()
        
        var elementsRemoved = 0
        for i in 0..<frequencies.count {
            elementsRemoved += frequencies[i]
            if elementsRemoved > k {
                return frequencies.count - i
            }
        }
        
        return 0
    }
}

Ставь 👍 и забирай 📚 Базу знаний