题解 | #那些插队的人#

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

输入：
3,[3, 2, 3]
返回值：
2
说明：
初始队伍为 [1, 2, 3]
3 开始插队 [3, 1, 2]
2 开始插队 [2, 3, 1]
3 开始插队 [3, 2, 1]
所以2还在原来的位置，3和1两个人已经不在原来的位置了。

方法一：暴力解法
用map存储队伍中的元素，键代表元素，值代表元素所处位置，模拟元素插队的过程，遍历插队元素编号，每次一个元素插队，排在插队元素前面的元素均要往后挪一位，这里修改代表插队元素键所对应的值，排在插队元素后面的元素位置不变，插队元素本身的位置改为1，最后遍历队伍，统计位置改变的元素数量。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算有多少个人最终不在自己原来的位置上
     * @param n int整型 队伍总长
     * @param cutIn int整型一维数组 依次会插队到最前方的人的编号
     * @return int整型
     */
    public int countDislocation (int n, int[] cutIn) {
        // write code here
        Map<Integer,Integer>map=new HashMap<>();
        //将队伍中的元素放入map
        for(int i=1;i<=n;i++){
            map.put(i,i);
        }
        for(int m:cutIn){
            //temp暂时存储要插队的元素的位置
            int temp=map.get(m);
            for(int i=1;i<=n;i++){
                if(map.get(i)<temp)
                    map.put(i,map.get(i)+1);
            }
            map.put(m,1);
        }
        int res=0;
        for(int i=1;i<=n;i++){
            if(map.get(i)!=i)
                res++;
        }
        return res;
    }

}

复杂度：
时间复杂度：和在没有发生hash冲突的情况下时间复杂度都是,最差情况是，双重循环，最坏情况下时间复杂度高达
空间复杂度:用存储个元素，
(n为原始队伍的大小）
方法二：优化解法
暴力解法的时间复杂度和空间复杂度都相当高，虽然可以过全部的测试案例，但是我们应该寻求更好的解决方法
思路：

• 只需要看每个元素的最后一轮插队（包括重复插队的元素），插队元素的最终位置只取决于它最后一轮的插队，因此，从前往后遍历插队队伍,将元素存储在Hashset中（去重作用）

• 找出插队队伍中的最大值：我们可以把队伍分成两部分，位于最大值后面的元素属于未插队元素，位于最大值前面的元素属于插队元素，我们只需要统计插队元素中位于非正确位置的元素个数、

• 用nums数组保存逆序且去重后的插队队伍

• 通过判断插队元素的位置和序号是否匹配统计位于正确位置的元素个数，结果等于插队元素个数-插队元素中位于正确位置的元素个数

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算有多少个人最终不在自己原来的位置上
     * @param n int整型 队伍总长
     * @param cutIn int整型一维数组 依次会插队到最前方的人的编号
     * @return int整型
     */
    public int countDislocation (int n, int[] cutIn) {
        // write code here
        Set<Integer>set=new HashSet<>();
        int m=cutIn.length;
        int j=0,max=0,right=0;
        int[]nums=new int[n];
        //从后往前遍历cutIn，以最后一次插队为结果
        for(int i=m-1;i>=0;i--){
            //用set去重
            if(!set.contains(cutIn[i])){
                nums[j++]=cutIn[i];
                set.add(cutIn[i]);
                max=Math.max(max,cutIn[i]);
            }
        }
        //找出插过队的元素中最后处于正确位置元素的个数
        for(int i=0;i<max;i++){
            if(nums[i]==i+1)
                right++;
        }
        return max-right;
    }
}

复杂度：
时间复杂度：只有一层循环，所以时间复杂度为
空间复杂度：使用额外的Hashset大小不超过m,空间复杂度为
(m为插队数组的大小）