c++一道关于栈的题超时TLE

Question

问题描述
一副纸牌包括
n 张牌。每张卡都不同，编号从
1∼n。
最初，卡片是从
1∼n,我们通过以下方式完成随机播放过程：
在每个操作中，我们将抽出一张卡片并将其放置在第一张卡片的位置，然后重复执行此操作
m次。
输出
m次操作后卡的顺序。
输入项
输入的第一行包含两个正整数
n,m
接下来是
m行，每行都有一个正整数
s，代表由提取到第一张的卡号。
输出量
输出
m次操作后卡的顺序，每个数字后应有一个空格。

输入样例
5 3
3
4
3
输出样例
3 4 1 2 5
数据规模
对于
20%的数据
1≤n,m≤10^3
对于
100%的数据
1≤n,m≤10^5
代码：

#include <bits/stdc++.h>
using namespace std;
stack<int>s1,s2;
int main()
{
    int n,m;
    cin >> n >> m;
    for(int i=n;i>=1;i--)
    {
        s1.push(i);
    }
    while(m--)
    {
        int num;
        cin >> num;
        while(s1.top()!=num)
        {
            s2.push(s1.top());
            s1.pop();
        }
        s1.pop();
        while(!s2.empty())
        {
            s1.push(s2.top());
            s2.pop();
        }
        s1.push(num);
    }
    while(!s1.empty())
    {
        cout<<s1.top()<<" ";
        s1.pop();
    }
    return 0;
}

这个超时了，该怎样优化呢？还有能不能帮我分析一下我这个代码的时间复杂度

Answer 1

以下回复参考：皆我百晓生、券券喵儿等免费微信小程序作答:

首先，我们来分析一下你的代码的时间复杂度。在最坏的情况下，每次抽取的卡片都不在栈顶，所以你需要将栈中的卡片移动到另一个栈，然后再移回来。这个过程的时间复杂度是O(n)。因为你需要进行m次这样的操作，所以总的时间复杂度是O(mn)。

对于优化，我们可以使用一个哈希表（例如unordered_map）来存储每张卡片的位置，这样我们就可以在O(1)的时间内找到并移除一张卡片。然后，我们可以使用一个数组来模拟栈，因为数组的插入和删除操作的时间复杂度都是O(1)。以下是优化后的代码：

#include <bits/stdc++.h>
using namespace std;
unordered_map<int, int> pos;
vector<int> s;
int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; i++)
    {
        s.push_back(i+1);
        pos[i+1] = i;
    }
    while(m--)
    {
        int num;
        cin >> num;
        int index = pos[num];
        if(index != 0)
        {
            s.erase(s.begin() + index);
            pos.erase(num);
            for(int i = index; i < s.size(); i++)
            {
                pos[s[i]] = i;
            }
        }
        s.insert(s.begin(), num);
        pos[num] = 0;
    }
    for(int i = 0; i < n; i++)
    {
        cout << s[i] << " ";
    }
    return 0;
}

这个代码的时间复杂度是O(m)。