思路:
题目的主要信息:
- 长度为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的空间