解题思路

1. 基本思路

我们需要在原序列中挑选出一个长度为k的子序列，要求该子序列包含1, 2, ..., k，且每个数字只出现一次。字典序最小意味着我们在每一步选择时，要尽可能选择一个较小的数字。

2. 栈结构

为了解决这个问题，我们可以使用栈（Stack）来辅助选择数字。栈结构的特点是后进先出（LIFO），可以帮助我们在遍历过程中保持字典序最小。

3. 具体步骤

1. 倒序遍历：从左到右遍历整个序列，但在选择时，需要考虑后面是否还有该数字。如果后面没有该数字了，那么该数字必须被选中。

2. 栈的使用：我们使用栈来存储已经选择的数字，确保字典序最小。

   • 当栈顶的数字比当前数字大，并且栈顶数字后面还有更多的数字时，我们可以弹出栈顶数字，选择当前数字。
   • 每次选择时，尽量保证栈中的数字是递增的，这样才能确保字典序最小。

3. 避免重复选择：每个数字最多选择一次，因此我们需要用一个数组记录每个数字是否已经被选择过。

4. 复杂度分析

• 遍历序列一次，每个数字最多入栈一次或出栈一次，因此时间复杂度为O(n)。
• 空间复杂度为O(k)，用于存储最终的子序列。

代码实现

Python代码实现

def find_subsequence(n, k, a):
    # 用栈来构建最终的子序列
    stack = []
    # 记录每个数字是否已经选择过
    in_stack = [False] * (k + 1)
    # 记录每个数字在后续序列中的出现次数
    count = [0] * (k + 1)

    # 统计每个数字出现的次数
    for num in a:
        count[num] += 1

    # 遍历序列
    for num in a:
        count[num] -= 1  # 当前数字已经处理过，剩余的次数减少

        # 如果栈中已经有该数字，则跳过
        if in_stack[num]:
            continue

        # 如果栈顶的数字比当前数字大，并且栈顶的数字在后面还会出现，那么就弹出栈顶
        while stack and stack[-1] > num and count[stack[-1]] > 0:
            # 弹出栈顶数字
            in_stack[stack.pop()] = False

        # 将当前数字加入栈中
        stack.append(num)
        in_stack[num] = True

    return stack


# 输入处理
n, k = map(int, input().split())
a = list(map(int, input().split()))

# 获取字典序最小的子序列
result = find_subsequence(n, k, a)

# 输出结果
print(" ".join(map(str, result)))

Java代码实现

import java.util.*;

public class Main {
    public static List<Integer> findSubsequence(int n, int k, int[] a) {
        Stack<Integer> stack = new Stack<>();
        boolean[] inStack = new boolean[k + 1];
        int[] count = new int[k + 1];

        // 统计每个数字的出现次数
        for (int num : a) {
            count[num]++;
        }

        for (int num : a) {
            count[num]--;

            // 如果栈中已经有该数字，跳过
            if (inStack[num]) {
                continue;
            }

            // 如果栈顶的数字比当前数字大，并且栈顶的数字在后面还会出现，则弹出栈顶
            while (!stack.isEmpty() && stack.peek() > num && count[stack.peek()] > 0) {
                inStack[stack.pop()] = false;
            }

            // 将当前数字加入栈中
            stack.push(num);
            inStack[num] = true;
        }

        return stack;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }

        List<Integer> result = findSubsequence(n, k, a);
        for (int num : result) {
            System.out.print(num + " ");
        }
    }
}

C++代码实现

#include <bits/stdc++.h>
using namespace std;

vector<int> findSubsequence(int n, int k, vector<int>& a) {
    stack<int> s;
    vector<bool> inStack(k + 1, false);
    vector<int> count(k + 1, 0);
    vector<int> result;

    // 统计每个数字的出现次数
    for (int num : a) {
        count[num]++;
    }

    // 遍历序列
    for (int num : a) {
        count[num]--;

        // 如果栈中已经有该数字，跳过
        if (inStack[num]) {
            continue;
        }

        // 如果栈顶的数字比当前数字大，并且栈顶的数字在后面还会出现，则弹出栈顶
        while (!s.empty() && s.top() > num && count[s.top()] > 0) {
            inStack[s.top()] = false;
            s.pop();
        }

        // 将当前数字加入栈中
        s.push(num);
        inStack[num] = true;
    }

    // 将栈中的元素存入结果
    while (!s.empty()) {
        result.push_back(s.top());
        s.pop();
    }

    // 因为栈是从后向前存的，所以要反转结果
    reverse(result.begin(), result.end());
    return result;
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<int> result = findSubsequence(n, k, a);
    for (int num : result) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

题目内容

现在有一个长度为$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$个数字，表示字典序最小的子序列。不要输出行末空格。

样例1

输入

5 3
2 1 3 3 2

输出

1 3 2

说明

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