题目：那些插队的人
描述：你有一个长度为 n 的队伍，从左到右依次为 1~n，有 m 次插队行为，用数组 cutIn 进行表示，cutIn 的元素依次代表想要插队的人的编号，每次插队，这个人都会直接移动到队伍的最前方。你需要返回一个整数，代表这 m 次插队行为之后，有多少个人已经不在原来队伍的位置了。
示例1：输入：3,[3, 2, 3]，返回值：2
说明：
初始队伍为 [1, 2, 3]
3 开始插队 [3, 1, 2]
2 开始插队 [2, 3, 1]
3 开始插队 [3, 2, 1]
所以2还在原来的尾置，3和1两个人已经不在原来的位置了。

解法一：
思路分析：这道题应该属于一道非常有趣的数学问题，在此说明，礼貌排队，不要插队，在长度为n的队伍中，有m次插队的行为，插队者在数组中有编号，如果该编号想要插队的话就将该编号直接存放在数组的首位，然后依次循环，当插队结束，统计一下有多少人不在原先的位置即可，这就是本题的大意。
实例分析：输入：3,[3, 2, 3]
图片说明
——由上述分析可以清晰的看到3和1的位置发生了改变，所以输出2
——我们根据上表进行分析，队伍在排列的过程中主要是由最后一次插队所决定的，没插队的人始终会排列在插队人的后面（没插队的人是最倒霉的）因此我们只需要遍历cutIn数组，当有重复的人就把他抛过，需要统计有多少人不在原位置，我们也可以统计有多少人在原位置，然后将总的人数减去在原位置的人数，最终得到的就是不在原位置的人数，因为有的人会插队，所以在排列的过程会有两种人需要进行计算，对于插队的人，需要判断当前位置是否与原序号相匹配，对于没插队的人，我们只要判断插队的人的最大序号，大于最大序号的人一定还在原来的队伍中，小于最大序号的人一定不在原序号中，所以据此分析即可完成相应的统计。
——首先我们设定三个值，表示插队的最大序号数，表示还在原位置的人，表示正常的序号。对cutIn数组进行遍历循环，存在没有插过队也就是false，就执行if语句，在if语句中，主要判断三个点，最大序号数，位置不变的，插过队的记为true，最后使用就可以得到最终的结果。
举例说明：输入：7,[3，2，3，5，1]
代码执行过程：
图片说明
正常分析过程：
图片说明
结合上下表格，就能得出最终的结果。
C++核心代码为：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算有多少个人最终不在自己原来的位置上
     * @param n int整型 队伍总长
     * @param cutIn int整型vector 依次会插队到最前方的人的编号
     * @return int整型
     */
    int countDislocation(int n, vector<int>& cutIn) {
        // write code here
        int len = cutIn.size();//插队的人总数，含重复的
        if(len == 0)//没有人插队，返回0
            return 0;
        int maxl = 0;
        vector<bool> dp(n + 1, false);//初始化n个人，初始值false
        int common = 0;
        int count = 0;
        for(int i = len - 1; i >= 0; i--){
            if(!dp[cutIn[i]]){//没有插队的执行，重复插队的就不考虑了
                maxl = max(maxl, cutIn[i]);
                if(cutIn[i] == ++count)
                    //因为是从最后开始循环的，所以1 = 1类似的重合
                    common++;
                dp[cutIn[i]] = true;//变了设为true
            }
        }
        return maxl - common;
    }
};

上述代码有一个for循环用来循环数组的长度N，所以其时间复杂度为，设定了额外的内存空间dp用来存储访问过的插队人数，所以空间复杂度为。

解法二：
思路分析：我们通过解法一发现，每一次插队的人的位置和其最后一次插队有关，就比如输入：7,[3，2，3，5，1]，第一个3和第三个3，在顺序遍历的情况下第一个3没什么用，这也是为什么在解法一种不执行最后一步的原因，我们使用set和vector结合来解决，首先通过逆序遍历计算出前n个变的值的总数，通过对前n个数进行判断来求解。其中检测容器set1，用来存放第一次出现的数，存放容器res，用来存放所有人插完队后，插队人的容器。
C++核心代码为：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算有多少个人最终不在自己原来的位置上
     * @param n int整型 队伍总长
     * @param cutIn int整型vector 依次会插队到最前方的人的编号
     * @return int整型
     */
    int countDislocation(int n, vector<int>& cutIn) {
        // write code here
        if (cutIn.size() == 0 || n <= 1){
            return 0;
        }
        unordered_set<int> s1;//用来存放第一次出现的数
        vector<int> res;//存放容器
        int max = 1;
        int len = cutIn.size();
        for(int i = len - 1;i >= 0;i--){
            int index = cutIn[i];//index接收cutIn的值
            if(s1.find(index) == s1.end())//没有找到
            {
                s1.insert(index);//在s1中添加该数
                res.push_back(index);//将该数放入res容器中
                max = index > max ? index : max;//记录最大值
            }
        }
        int result = max;//记录不在原位置的值
        for(int i=0;i<res.size();i++){//该数在原位置上，那么result减一
            if(res[i] == i+1){
                result--;
            }
        }
        return result;
    }
};

——该算法首先需要循环找到最大序号值的元素，然后再循环判断序号值与值是否相同，所以其时间复杂度还是，空间复杂度借助了一个set容器和vector容器，所以空间复杂度为。
解法三：
思路分析：也可以使用暴力法进行分析，首先给定一个容器v1记录1 - n的容器，且赋予初始值false，还需要给定一个容器v2复制一份v1的值用来跟对比后的v1进行比较记录，然后进行逐个遍历最终确定变了序号的人的数量，该方法循环次数多，且占用内存空间大，所以就不进行代码展示。