有一个序列 a 长度为 n. 可以选择序列中两个数字 ai 和 aj (i != j, 1 <= i, j <= n) 如果 ai = aj 将其中一个数更改为 0. 否则,将它们都更改为它们之中最小的数。 需要将序列中的数字都更改为 0. 请你求出最小操作次数。
时间: 2024-02-18 21:05:18 浏览: 131
将数字变成 0 的操作次数1
对于这个问题,我们可以先统计序列中每个数出现的次数。然后对于相同的两个数,我们可以将其中一个数更改为 0,操作次数加 1。对于不同的两个数,我们将它们都更改为它们之中最小的数,操作次数也加 1。最后,我们只需要将所有数都更改为 0,操作次数再加上序列中不同的数的个数即可。
以下是具体实现的伪代码:
```
count = {}
distinct = 0
for i in range(n):
if a[i] in count:
count[a[i]] += 1
else:
count[a[i]] = 1
distinct += 1
ans = 0
for k, v in count.items():
if v > 1:
ans += 1
distinct -= 1
ans += distinct
```
其中 count 用于统计每个数出现的次数,distinct 表示不同的数的个数,ans 表示操作次数。
阅读全文