题解 | #那些插队的人#

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

方法一：遍历的思想

求解思路
对于本题目，我们可以将队伍中的人分为没插过队的和插过队的两种，在最后的排队中，没插过队的都在后面，插过队的最大值是个分界线，没插过队的且小于这个分界线的最后一定不在原来的位置，没插过队的且大于这个分界线的一定在原来的位置。因此我们从后往前看，删除重复的之后，直接统计插过队的还在原来位置上的人数即可。

图片说明

解题代码

class Solution:
    def countDislocation(self , n , cutIn ):
        cd = set()
        m = len(cutIn)
        if m == 0:
            return 0
        myres = max(cutIn) # 赋最大值
        for i in range(m-1,-1,-1): # 倒序遍历
            if cutIn[i] not in cd:
                if cutIn[i]==len(cd)+1:
                    myres-=1 # 插队的情况，结果减1
                cd.add(cutIn[i])
        return myres # 返回结果

复杂度分析
时间复杂度：一层循环，因此时间复杂度为 $O(N)$
空间复杂度：引入哈希表，使用额外的内存地址空间，因此空间复杂度为 $O(N)$

方法二：逆向的思想

求解思路
对于本题，我们可以发现，队伍最终的排列是由最后一次插队决定的，然后没插队的人全部依次排在插队的人的后面，因此从后往前遍历cutln数组，遇到重复的跳过。对于判断是否还在原位置的问题，将队伍分为两部分进行计算，分别为插队的人和没插队的人。对于插队的人直接判断位置和序号是否匹配，对于没插队的人，如果其序号大于插队的人中的最大序号，则一定还在原来的队伍中的位置。如果其序号小于插队的人中的最大序号，则一定不在原来的位置。

图片说明

解题代码

import java.util.*;
public class Solution {
    public int countDislocation (int n, int[] cutIn)
    {
        if(cutIn.length == 0) return 0; // 个别情况单独讨论
        HashMap<Integer, Boolean> myvisited = new HashMap<>(); // 声明哈希表
        int max = 0, same = 0, number = 1;
        for(int i = cutIn.length - 1; i >= 0; i--) 
        {
            if(!myvisited.containsKey(cutIn[i])) // 判断是否包含
            {
                myvisited.put(cutIn[i], true);
                if(cutIn[i] == number++) same++;
                max = Math.max(max, cutIn[i]); // 计算max值
            }
        }
        return max - same; // 返回结果
    }
}

复杂度分析
时间复杂度：一层循环，因此时间复杂度为 $O(N)$
空间复杂度：引入哈希表，使用额外的内存地址空间，因此空间复杂度为 $O(N)$