插队的人解题

其中n <= 1e9，创建数组进行模拟插队会超内存，不可行。只能找规律。

• 我们可以从cutIn中找到编号的最大值，在他之后的队伍没有参与插队，位置不变
• cutIn中会存在通过插队还在原来位置上的人，将cutIn倒序，且去重，就是最终的前len个人

class Solution {
public:
    /**
     * 计算有多少个人最终不在自己原来的位置上
     * @param n int整型 队伍总长
     * @param cutIn int整型vector 依次会插队到最前方的人的编号
     * @return int整型
     */
    int countDislocation(int n, vector<int>& cutIn) {
        // write code here
        if(n == 1 || cutIn.empty()) return 0;
        int len = cutIn.size();
        //计算插队编号的最大值，该编号之后的队伍位置不变
        int maxV = cutIn[0];
        for(int i = 1; i < len; i++){
            if(cutIn[i] > maxV){
                maxV = cutIn[i];
            }
        }
        int part_1 = n - maxV;
        //计算已经打乱顺序的队伍，有哪些人通过插队还在原来的位置上
        //将cutIn倒序，且去重，就是最终的前len个人
        set<int> set;
        int part_2 = 0;
        int index = 1;
        for(int i = cutIn.size() - 1; i >= 0; i--){
            if(set.find(cutIn[i]) == set.end()){
                set.insert(cutIn[i]);
            }else{
                continue;
            }
            if(cutIn[i] == index){
                part_2++;
            }
            index++;
        }
        return n - (part_1 + part_2);
    }
};