MEX的MEX

柿子饼同学

有一个题目: 给出一个数组, 求这个数组中所有区间的 mex 的 mex

mex(S) 表示 S 中最小的没有出现的正整数

没思路 , 求解

柿子饼同学

额 , 想出来了
用线段树 , 记录每个值上次出现的下标, 扫一遍 , 记下来然后枚举即可

isdkz

问题描述中要求求解给定数组中所有区间的 mex 的 mex。首先需要理解 mex(S) 的定义，即 S 中最小的没有出现的正整数。

解决这个问题的一种方法是使用暴力法，即对于给定数组中的每个区间，计算该区间的 mex 值，并将所有区间的 mex 值保存在一个数组中，然后再对这个数组求 mex 值。

具体步骤如下：

1. 遍历数组中的每个起始位置 i，从 i 开始遍历数组的每个结束位置 j。
2. 对于每个区间 [i, j]，创建一个集合 set，用于存储区间中出现的正整数。
3. 在区间 [i, j] 中遍历每个元素，将其加入集合 set 中。
4. 在集合 set 中找到最小的没有出现的正整数，即 mex 值。
5. 将 mex 值添加到一个新的数组中。
6. 继续遍历下一个区间，重复步骤 3-5。
7. 对于得到的数组，再次计算其 mex 值，即为所求的结果。

下面是使用 Python 语言实现的代码：

def mex(S):
    i = 1
    while i in S:
        i += 1
    return i

def mex_of_mex(arr):
    n = len(arr)
    mex_arr = []
    for i in range(n):
        for j in range(i, n):
            interval = set(arr[i:j+1])
            mex_val = mex(interval)
            mex_arr.append(mex_val)
    return mex(mex_arr)

# 示例输入
arr = [1, 2, 3, 4, 5]

# 调用函数计算结果
result = mex_of_mex(arr)

# 输出结果
print(result)

以上代码中， mex  函数用于计算一个集合的 mex 值， mex_of_mex  函数用于计算给定数组的所有区间的 mex 的 mex 值。

对于示例输入  [1, 2, 3, 4, 5] ，输出结果为 3。

柿子饼同学

isdkz 发表于 2023-11-8 23:59
问题描述中要求求解给定数组中所有区间的 mex 的 mex。首先需要理解 mex(S) 的定义，即 S 中最小的没有出现 ...

额...