题目

牌堆里有n张扑克牌，有m次操作，每次操作将对应的牌放到牌堆顶，求最后牌堆的序列。

输入序列为从牌堆顶到牌堆底。1 <= n, m <= 1e5

示例

输入：
5
1 2 3 4 5
3
3 2 3
输出：
3 2 1 4 5

思路

如果直接模拟每一次放堆顶操作，不管用链表还是数组都需要 O(n) 的时间复杂度去找到对应的牌或者调整牌序，总的复杂度就是 O(mn)，不满足要求。

其实并不需要模拟每次操作，只需要关注对每一张牌的最后一次操作，这些操作序列才最终决定了牌堆的顺序。

解法

  1. 反向遍历操作数组，每次遇到未出现的数 x，说明这是x的最后一次操作，将其加入答案数组和标记集合中；

  2. 正向遍历牌堆数组，每次遇到不在标记集合中的数y，说明 y从未被操作过，将其加入答案数组。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
#include <iostream>
using namespace std;

template<typename T>
inline void printVec(vector<T> v) {
    cout << "vector: ";
    for (size_t i=0; i<v.size(); ++i) {
        cout << v[i] << (i < v.size()-1 ? " " : "");
    }
    cout << endl;
}
template<typename T>
inline void printSet(unordered_set<T> st) {
    cout << "set: ";
    for (auto iter = st.begin(); iter != st.end(); iter++) {
        cout << *iter << " ";
    }
    cout << endl;
}

int main() {
    int n, m;
    cin >> n;
    vector<int> nums(n);
    for (int i=0; i<n; ++i) {
        cin >> nums[i];
    }
    cin >> m;
    vector<int> ops(m);
    for (int i=0; i<m; ++i) {
        cin >> ops[i];
    }
    unordered_set<int> st;
    vector<int> res;
    for (auto iter = ops.rbegin(); iter != ops.rend(); iter++) { // 反向遍历操作序列
        auto num = *iter;
        if (st.find(num) == st.end()) {
            res.emplace_back(num);
            st.insert(num);
        }
    }
    // printSet(st);
    for (int num : nums) { // 正向遍历牌堆
        if (st.find(num) == st.end()) {
            res.emplace_back(num);
        }
    }
    printVec(res);
    return 0;
}
  • 时间复杂度 O(n+m)
  • 空间复杂度 O(n)

扩展

面试官是个ACM选手，问有没有其他空间复杂度 O(1) 的方法 😭
“下次一定” 👌 “明天再说“ 🙉 晚安 🛌