Сложность: 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:
def minSetSize(self, arr: List[int]) -> int:
arr.sort()
counts = []
current_run = 1
for i in range(1, len(arr)):
if arr[i] == arr[i - 1]:
current_run += 1
continue
counts.append(current_run)
current_run = 1
counts.append(current_run)
counts.sort(reverse=True)
numbers_removed_from_arr = 0
set_size = 0
for count in counts:
numbers_removed_from_arr += count
set_size += 1
if numbers_removed_from_arr >= len(arr) // 2:
break
return set_size
Ставь 👍 и забирай 📚 Базу знаний