题意

你有一个长度为 n 的队伍，从左到右依次为 1~n，有 m 次插队行为，用数组 cutIn 进行表示，cutIn 的元素依次代表想要插队的人的编号，每次插队，这个人都会直接移动到队伍的最前方。你需要返回一个整数，代表这 m 次插队行为之后，有多少个人已经不在原来队伍的位置了。

题解

如何写一份正确的代码？

这道题目非常容易模拟。首先我们需要一个长度为n的数组，这个数组存储了这n个位置的队列分别都站着哪些人，就如同样例解释里面的一样。我们要做的，就是模拟题目中描述的整个过程。

  • 找到每次想要插队的那个人
  • 把他移动至队伍的前端

这两个步骤都非常容易实现。具体而言，就类似于选择排序。在选择排序中，我们每次都是选择一个当前未排序数组中最小的那个元素，然后把它移动到已排序数组的后面。我们这个题目的过程也和这个类似。而将这个人移动到队伍的最前端，也就是需要将他前面的所有人全部往后挪动一个位置，然后把他放在最前面。显然，这是一个非常大的时间消耗。

最后一步，我们需要做什么？就是扫描一遍这n个元素的数组，然后将不站在自己原来位置上的人的个数输出出来对吧。这样总时间复杂度就是 O(nm) 的，空间复杂度是 O(n)的。因为对于每个想要插队的人，他都可能导致整个队伍的变动。

如何写一份能够通过此题的代码？

我们必须注意到的一点就是，此题中的n非常大，而m非常小。所以我们必须针对m进行优化。首先可以注意到的一点就是，至始至终，有些人的相对位置是一直没有改变的。如果a,b两人之间没有任何想要插队的人，那么这两个人的相对位置就一直不会改变。所以我们可以把相对位置没有发生改变的人分为一组，其实这一组要么是一个插队的人，要么是两个相邻的插队的人中间的一段人。这样划分下来，最多有 2m + 1组相对位置不会发生变化的人。所以我们可以直接将一组人开一个节点进行表示。这样总共拥有的数据量也就是 O(m) 的。最后依旧进行模拟，时间复杂度是 O(m^2)，如果使用运行速度较块的 c++ 语言，再加上比较小的常数实现方法，可能可以卡常通过此题。

如何写一份肯定能够通过此题的代码？

我们需要继续观察题目的性质。首先可以注意到的是，把一个人往前挪动，是不会影响他身后的人的位置的。这一点信息很重要，也就是说，不在自己位置上的人，一定是在最后一个插队的人之前！
同时需要注意到另外一个重要的性质：如果一个人没有向前插队，而且在最大的编号之前，那么一定会向后挪动，不再位于自己的位置上。
所以我们只需要考虑曾经插队过的人有没有恰好回到自己的原位上就好了。
所以最终求解答案的时候，我们只需要知道曾经插队的人，有没有回到自己的位置上就好了。维护这些插队的人的位置非常简单。因为都是向第一个位置插队，那么越晚插队的人排的位置就越靠前，所以只需要保留每个插队的人最后在插队列标里出现的位置就好。然后逆序就是每个插队的人的位置。

如果使用平衡树作为set的实现方法，那么这道题目的时间复杂度就是 O(mlogm) 的，如果使用hash表作为set的实现方法，那么这道题目的时间复杂度就是 O(m) 的，非常优秀，不需要担心超时。

代码

class Solution {
public:
    /**
     * 计算有多少个人最终不在自己原来的位置上
     * @param n int整型 队伍总长
     * @param cutIn int整型vector 依次会插队到最前方的人的编号
     * @return int整型
     */
    int countDislocation(int n, vector<int>& cutIn) {
        // write code here
        set<int>app;
        vector<int>ord;
        int mx = 0;
        for (int i = cutIn.size() - 1; i >= 0; i--)  {
            int id = cutIn[i];
            if (app.find(id) == app.end()) {
                ord.push_back(id);
                app.insert(id);
            }
            mx = max(mx, id);
        }
        int ans = mx;
        for (int i = 0; i < ord.size(); i++)
            if (ord[i] == i + 1)
                ans--;
        return ans;
    }
};