题解 | #那些插队的人#

思路：

题目的主要信息：

• 长度为n为队伍，人员编号1-n
• cutIn数组中是要插队的编号，依次进行插队，即加入到最前面
• 求最后有多少人不在原来的位置

方法一：哈希表
具体做法：
对于最后的队列，没有插过队的人肯定都排在后面，最大插队元素是其分界线，最大插队元素之前的位置都可能有改变，之后的就不会有变化，如果没有重复，它就是严格分界线。
因为我们只要最大插队元素，然后减掉重复的元素，即可得到位置改变的人数。
去重可以用哈希表。

class Solution {
public:
    int countDislocation(int n, vector<int>& cutIn) {
        int m = cutIn.size();
        if(m == 0) //没有人插队
            return 0;
        int maxe = *max_element(cutIn.begin(), cutIn.end()); //找到最大插队元素
        unordered_map<int, int>mp;
        for(int i = m - 1; i >= 0; i--){
            if(mp.find(cutIn[i]) == mp.end()){ 
                if(cutIn[i] == mp.size() + 1)//如果插队编号等于已插队人数+1，则处于原来的位置
                    maxe--; //减去留在原来位置的人
                mp[cutIn[i]]++; //加入插队哈希表
            }
        }
        return maxe;
     }
};

复杂度分析：

• 时间复杂度：，一次遍历，循环外的max_element函数也是
• 空间复杂度：，辅助哈希表最大空间

方法二：逆向考虑
具体做法：
我们也可以换一种思路，有多少人不在原来的位置，就是最大的插队元素减去最大插队元素之前位置还没变的。求位置没变的情况，如图所示，我们可以逆向考虑，当某个插队元素与逆向次序相等时，我们则认定其为不变的。不过我们需要一个辅助数组记录该元素是否已经插过队，避免重复。

class Solution {
public:
    int countDislocation(int n, vector<int>& cutIn) {
        int m = cutIn.size();
        if(m == 0) //没有人插队
            return 0;
        int maxe = 0;
        int repeat = 0;
        int count = 0;
        vector<bool> dp(n + 1, false); //下标对应人的编号
        for(int i = m - 1; i >= 0; i--){
            if(!dp[cutIn[i]]){ //没有插过队
                maxe = max(maxe, cutIn[i]); //迭代找最大插队人员
                if(cutIn[i] == ++count)
                    repeat++;
                dp[cutIn[i]] = true;
            }
        }
        return maxe - repeat;
     }
};

复杂度分析：

• 时间复杂度：，一次遍历
• 空间复杂度：，辅助数组dp的空间