Задача: 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 {
    function minSetSize($arr) {
        sort($arr);
        
        $counts = [];
        $currentRun = 1;
        for ($i = 1; $i < count($arr); $i++) {
            if ($arr[$i] == $arr[$i - 1]) {
                $currentRun += 1;
                continue;
            }
            $counts[] = $currentRun;
            $currentRun = 1;
        }
        $counts[] = $currentRun;
        
        rsort($counts);
        
        $numbersRemovedFromArr = 0;
        $setSize = 0;
        foreach ($counts as $count) {
            $numbersRemovedFromArr += $count;
            $setSize += 1;   
            if ($numbersRemovedFromArr >= count($arr) / 2) {
                break;
            }
        }
        
        return $setSize;
    }
}

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