题解 | #mex#
mex
https://www.nowcoder.com/practice/da138098ed74405db63e0d75a9878acc
题目链接
题目描述
给定一个由 个非负整数组成的数组。一轮操作定义为：首先计算数组的
（未在数组中出现的最小非负整数），然后将数组中的每个数
更新为
。求至少需要多少轮操作才能使数组中的每个数都相同。如果不可能，则输出 -1。
解题思路
本题要求计算最少需要多少轮操作才能使数组中的所有元素都相同。直接模拟操作在数组规模和数值范围较大时会超时，因此我们需要找到一个数学规律来直接计算答案。
首先，我们处理几个基本情况：
- 初始状态已满足：如果数组中的所有元素在开始时就已经相同，那么所需的操作轮数就是 0。
- 不可能完成：如果数组元素不相同，那么唯一可能达成的相同状态就是所有元素都变为0。要让数变小，
mex必须大于0，这意味着数组中必须要有0这个数。因此，如果一个元素不相同的初始数组里不包含0，则永远无法完成目标，答案为 -1。
接下来，对于一般情况（元素不相同，且包含0），我们可以通过分析模拟过程的轮数变化，推导出一个数学公式。
设数组去重并排序后，所有的正数构成为 。
-
基准情况：想象一下，如果数组中只有一个正数
（以及0）。我们需要
轮
mex=1的操作将，此时数组变为
{0, 1}。然后再需要mex=2的操作将其变为{0}。总轮数为。
-
引入中间数：现在，我们考虑数组中有多个正数的情况，如 `{0, p_1, p_k}}
p_1 < p_k$)。
- 首先，经过
轮操作后（
轮简单操作 + 1 轮复杂操作），数组
{0, p_1}的部分会变成{0}。 - 在这
。
- 整个过程相当于我们花费了
- 解决这个子问题还需要
。
- 首先，经过
-
推广规律：进一步推导可以发现，每当我们多一个不同的正数（除了最大的那个），总轮数就会减少1。这可以理解为，较小的正数在被消除的过程中，“顺便”帮助较大的正数减小了数值，从而节省了轮数。
最终公式：
若去重后的正数有 个，最大值为
，则总轮数 =
。
这个解法避免了复杂的模拟，只需要对输入数组去重、排序，然后根据正数的数量和最大值即可计算出结果。
代码
#include <iostream>
#include <vector>
#include <numeric>
#include <set>
#include <algorithm>
using namespace std;
void solve() {
int n;
cin >> n;
set<long long> s;
for (int i = 0; i < n; ++i) {
long long x;
cin >> x;
s.insert(x);
}
if (s.size() == 1) {
cout << 0 << "\n";
return;
}
if (s.find(0) == s.end()) {
cout << -1 << "\n";
return;
}
// 提取所有正数
vector<long long> positives;
for (long long val : s) {
if (val > 0) {
positives.push_back(val);
}
}
long long k = positives.size();
if (k == 0) { // 只有0，但size不为1说明有重复的0，已满足
cout << 0 << "\n";
return;
}
long long pk = positives.back(); // set是有序的，转成vector后也是有序的
// 总轮数 = pk - (k - 1)
cout << pk - k + 1 << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
solve();
return 0;
}
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Set<Long> s = new TreeSet<>();
for (int i = 0; i < n; i++) {
s.add(sc.nextLong());
}
if (s.size() == 1) {
System.out.println(0);
return;
}
if (!s.contains(0L)) {
System.out.println(-1);
return;
}
// 提取所有正数
List<Long> positives = new ArrayList<>();
for (long val : s) {
if (val > 0) {
positives.add(val);
}
}
if (positives.isEmpty()) { // 只有0，但size不为1说明有重复的0，已满足
System.out.println(0);
return;
}
long k = positives.size();
long pk = positives.get(positives.size() - 1); // TreeSet是有序的
// 总轮数 = pk - (k - 1)
System.out.println(pk - k + 1);
}
}
def solve():
n = int(input())
a = list(map(int, input().split()))
s = set(a)
if len(s) == 1:
print(0)
return
if 0 not in s:
print(-1)
return
# 提取所有正数并排序
positives = sorted([x for x in s if x > 0])
if not positives: # 只有0，但len(s)不为1说明有重复的0，已满足
print(0)
return
k = len(positives)
pk = positives[-1]
# 总轮数 = pk - (k - 1)
print(pk - k + 1)
solve()
算法及复杂度
- 算法：数学
- 时间复杂度：
，主要开销在于对输入数字去重和排序。
- 空间复杂度：
或
，其中
是数组中不同值的数量，用于存储去重后的数字。
腾讯公司福利 1075人发布