算法思想一：遍历

解题思路：

可分为没插过队的和插过队的两种，最后的排队，没插过队的都在后面，插过队的最大值是个分界线。
没插过队的小于这个分界线最后一定不在原来的位置，大于的一定在原来位置，插过队的，我们从后往前看，删除重复的，就是排队序列
直接统计插过队的还在原来位置上的人数即可

代码展示：

Python版本

class Solution:
    def countDislocation(self , n , cutIn ):
        # write code here
        # 哈希表
        cd = set()
        m = len(cutIn)
        if m == 0:
            return 0
        # 插队的最大编号
        res = max(cutIn)
        # 倒序遍历
        for i in range(m-1,-1,-1):
            if cutIn[i] not in cd:
                # 如果当前人插队编号等于已插队的人数+1，则其还会处于原来位置
                if cutIn[i]==len(cd)+1:
                    # 去除还在原来位置的人
                    res-=1
                # 记录已插队的人
                cd.add(cutIn[i])
        return res

复杂度分析

时间复杂度：N表示插入数组的长度，遍历插队数组时间

空间复杂的：哈希表占用空间

算法思想二：逆向思维

解题思路：

先来看一个例子15 [10, 4, 6, 5, 9, 7, 3, 3, 9, 10]，我们来模拟一下插队过程。
第一次：10
第二次：4 10
第三次：6 4 10
第四次：5 6 4 10
第五次：9 5 6 4 10
第六次：7 9 5 6 4 10
第七次：3 7 9 5 6 4 10
第八次：3 7 9 5 6 4 10
第九次：9 3 7 5 6 4 10
第十次：10 9 3 7 5 6 4
最终位置：10 9 3 7 5 6 4 1 2 8 11 12 13 14 15

可以发现，队伍最终的排列是由最后一次插队决定的，然后没插队的人全部依次排在插队的人的后面。因此从后往前遍历cutIn数组，遇到重复的跳过。
判断是否还在原位置时，将队伍分为两部分计算：插队的人和没插队的人。对于插队的人，直接判断位置和序号是否匹配；设插队的人中最大序号为max，对于没插队的人，序号>max的一定还在原来队伍中的位置，<max的一定不在原来位置（结合生活实际，很好理解：我们在排队的时候，不太关心排在自己前面的人的位置变动，因为这不会影响到我们自己的等待时间，但是一旦排在自己后面的人插到自己前面，我们就会很不爽，因为这会造成自己的等待时间边长）
题目让求有多少个人已经不在原来队伍的位置，我们可以逆向思维计算有多少人还在原来的位置，然后减去这个值就能得到位置改变的总人数

下图展示了例子中队伍的判断情况：

代码展示：

JAVA版本

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算有多少个人最终不在自己原来的位置上
     * @param n int整型 队伍总长
     * @param cutIn int整型一维数组 依次会插队到最前方的人的编号
     * @return int整型
     */
    public int countDislocation (int n, int[] cutIn) {
        // write code here
        // 特殊情况
        if(cutIn.length == 0) return 0;
        // 初始化
        HashMap visited = new HashMap();
        int max = 0, same = 0, number = 1;
        // 倒序遍历计算位置不会变化的数量
        for(int i = cutIn.length - 1; i >= 0; i--) {
            if(!visited.containsKey(cutIn[i])) {
                // visited 记录遍历过的数字
                visited.put(cutIn[i], true);
                // 判断插入人数恰好是该人原位置，则 same++
                if(cutIn[i] == number++) same++;
                // 插队中找到最大的数，该数之前的位置都会变化，之后的都不会变化
                max = Math.max(max, cutIn[i]);
            }
        }
        return max - same;
    }
}

复杂度分析

时间复杂度：N表示插入数组的长度，遍历插队数组时间

空间复杂的：哈希表占用空间