思路:

题目的主要信息:

  • 长度为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的空间