hash表比arraylist占用空间更小

import java.util.*;
 
 
public class Solution {
    /**
     * 计算有多少个人最终不在自己原来的位置上
     * @param n int整型 队伍总长
     * @param cutIn int整型一维数组 依次会插队到最前方的人的编号
     * @return int整型
     */
    public int countDislocation (int n, int[] cutIn) {
        // write code here
        int maxm = 0;
        int cutnum = cutIn.length;
        int count = 0;
        int index = 1;
        HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
        for(int i=cutIn.length-1;i>=0;i--){
            if(!map.containsKey(cutIn[i])){
                map.put(cutIn[i],index++);
                if(cutnum - i==cutIn[i])
                    count++;
            }
            else
                cutnum--;
            if(cutIn[i]>maxm) //找到最大的数，后面的人位置都不变，前面的没插队的都会变。
                maxm = cutIn[i];
        }
        return maxm-count;
    }
}