Задача: 1338. Reduce Array Size to The Half
Сложность: medium

Дан массив целых чисел arr. Вы можете выбрать набор чисел и удалить все вхождения этих чисел из массива.

Верните минимальный размер набора, чтобы было удалено не менее половины целых чисел из массива.

Пример:

Input: arr = [3,3,3,3,5,5,5,2,2,7]
Output: 2
Explanation: Choosing {3,7} will make the new array [5,5,5,2,2] which has size 5 (i.e equal to half of the size of the old array).
Possible sets of size 2 are {3,5},{3,2},{5,2}.
Choosing set {2,7} is not possible as it will make the new array [3,3,3,3,5,5,5] which has a size greater than half of the size of the old array.

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

1⃣Отсортировать массив и создать список подсчета количества вхождений каждого числа.

2⃣Отсортировать список подсчета в порядке убывания.

3⃣Удалять числа из массива, начиная с наибольшего количества вхождений, пока не будет удалено не менее половины чисел массива. Вернуть размер множества удаленных чисел.

😎 Решение:

class Solution {
    func minSetSize(_ arr: [Int]) -> Int {
        var arr = arr
        arr.sort()
        
        var counts: [Int] = []
        var currentRun = 1
        for i in 1..<arr.count {
            if arr[i] == arr[i - 1] {
                currentRun += 1
                continue
            }
            counts.append(currentRun)
            currentRun = 1
        }
        counts.append(currentRun)
        
        counts.sort(by: >)
        
        var numbersRemovedFromArr = 0
        var setSize = 0
        for count in counts {
            numbersRemovedFromArr += count
            setSize += 1   
            if numbersRemovedFromArr >= arr.count / 2 {
                break
            }
        }
        
        return setSize
    }
}

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