P3347.第1题-子序列的字典序

1000ms

Difficulty: 5

所属公司 : 京东

算法与标签>栈

题目内容

现在有一个长度为 $n$ 的数字序列，每个数都在 $1$ ~ $k$ 的范围内，且 $1$ ~ $k$ 内每个数字都至少出现过一次。现在我们想在这里面找一个子序列，使得 $1$ ~ $k$ 恰好出现一次，且字典序最小。请你通过程序得出结果。

我们认为:

$B$ 是 $A$ 的子序列，当且仅当可以从 $A$ 中删掉 $0$ 个或任意个元素之后按照原来的顺序拼接起来得到 $B$ 。

序列 $A$ 的字典序小于 $B$ ，当且仅当存在一个位置 $k$ ，使得 $A[k]<B[k]$ 且 $A[i]=B[i],i=1...k-1$ 。

第一行两个空格隔开的正整数 $n$ 和 $k$ ;

第二行 $n$ 个空格隔开的正整数，表示该数字序列 $a_i$ 。 $1≤k≤n≤5*10^4,1≤a_i≤k$

输出一行 $k$ 个数字，表示字典序最小的子序列。不要输出行末空格。

输入

5 3
2 1 3 3 2

输出

1 3 2

说明

其中一种可行的方案为:2 {1} {3} 3 {2}，选定括号中的数字，构成子序列，可知此时字典序最小。

输入

预期输出（选填）