题意

初始长度为$nn$n的数组$aa$a,值也是1~n即$a_i=ia\_i=i$ai​=i

给定另一个操作数组$cutIncutIn$cutIn表示对上述数组的更改，每次在$aa$a中找到值为$cutI{n}_{i}cutIn\_i$cutIni​的，将这个值放到数组$aa$a的起始位置

求最终数组$aa$a中，位置和初始位置不同的有多少个

方法

暴力实现与数组平移（应该TLE 却没TLE）

按照题意。

1. 生成一个位置数组pos，每个位置上存有初始的值
2. 遍历数组cutIn,对每一个cutIn 在数组pos 中寻找
3. 每次找到 修改pos数组
4. 最后对比 数组每个位置的值，输出不同的值的个数

代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算有多少个人最终不在自己原来的位置上
# @param n int整型 队伍总长
# @param cutIn int整型一维数组 依次会插队到最前方的人的编号
# @return int整型
#
class Solution:
    def countDislocation(self , n , cutIn ):
        pos = [i+1 for i in range(n)]
        for ci in cutIn: # 模拟每一次
            for i in range(n): # 寻找ci这个人
                if pos[i] == ci: # 找到ci
                    pos = [ci] + pos[0:i] + pos[i+1:n] # 模拟插队动作
                    break
        return sum([i+1 != pos[i] for i in range(n)]) # 统计不一致的个数

复杂度分析

空间复杂度: 这里我们的空间和所有位置的数量一致，为$O\left(n\right)O(n)$O(n)

时间复杂度: 我们遍历了cutIn 数组，每次对原来数组的搜索和修改的代价最差为$nn$n, 所以总时间复杂度最差为$O\left(nm\right)O(nm)$O(nm)，（然而它AC了）

链表+索引表(应该TLE没有TLE)

上面我们虽然通过了题目，但是如果数据更严一点，时间复杂度肯定过不了，考虑每次搜索和修改的最差代价太大，希望能优化这个代价。

如果我们能够$O\left(1\right)O(1)$O(1)的时间对一个值进行搜索和插入到头部就好了

那么考虑 链表+索引表

链表 如果我们把数据变成链，以题目的样例 n=3，那么

也就是$0-1-2-3-40-1-2-3-4$0−1−2−3−4 构成了一个链，每个节点只用关心其前后的节点

然后是，样例里面的第一次操作：3号插队了

也就是$0-3-1-2-40-3-1-2-4$0−3−1−2−4 构成了一个链，每个节点只用关心其前后的节点

回到索引表里

什么发生了变化呢？

首先原来3左右两个点连接到了一起，$2-3-42-3-4$2−3−4 变成了$2-42-4$2−4, 这影响了左节点的右节点，和右节点的左节点。

然后是插入动作$0-10-1$0−1变成了$0-3-10-3-1$0−3−1,也就是头部的节点插入了当前值，那么$00$0的右节点，$11$1的左节点，和$33$3本身都变化了

我们把它们形式化一下，假设现在变动的是$vv$v

那么$v.left.right=v.rightv.left.right\; =\; v.right$v.left.right=v.right 原来的左右节点相连 $v.right.left=v.leftv.right.left\; =\; v.left$v.right.left=v.left

接下来 $vv$v 完成插入到头部

$v.left=0,v.right=0.rightv.left\; =\; 0,v.right\; =\; 0.right$v.left=0,v.right=0.right

然后原来头部的节点要知道插入了$vv$v

$0.right.left=v,0.right=v0.right.left\; =\; v,\; 0.right\; =\; v$0.right.left=v,0.right=v

因此$66$6步完成了一个点的操作。

剩余步骤和上面的方法一样

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算有多少个人最终不在自己原来的位置上
     * @param n int整型 队伍总长
     * @param cutIn int整型vector 依次会插队到最前方的人的编号
     * @return int整型
     */
    int countDislocation(int n, vector<int>& cutIn) {
        vector<pair<int,int> > lr(n+2,pair<int,int>{}); // 记录每个人 左侧的人 和他右侧的人
        for(int i = 0;i<n+2;i++){
            lr[i] = {i-1,i+1}; // 初始 分别是i-1和i+1
        }
        for(auto idx:cutIn){ // 模拟每一次插队
            // connect
            // 获取当前左右的人
            const int l = lr[idx].first; 
            const int r = lr[idx].second;
            // 因为要把idx移走，所以让它们变成相邻的
            lr[l].second = r;
            lr[r].first = l;
            // cut in
            // 获取头部的人
            const int root = lr[0].second;
            // idx插入头部
            lr[0].second = idx;
            lr[root].first = idx;
            // 更新idx左右的人
            lr[idx].first = 0;
            lr[idx].second = root;
        };
        int pos = 1;
        int idx = lr[0].second;
        int ans = 0;
        while(idx <= n){
            if(idx != pos)ans++; // 位置变化 计数+1
            pos++;
            idx = lr[idx].second;
        }
        return ans ;
    }
};

复杂度分析

空间复杂度: 这里我们的空间虽然是链表，但是记录的是每个点的左右节点，还是和所有位置的数量一致，为$O\left(n\right)O(n)$O(n)

时间复杂度: 我们遍历了cutIn 数组，每次对原来数组的搜索和修改的代价全部为6次，是常数。最开始建立初始值和最后计算不同的值，都遍历了1到n，所以总时间复杂度最差为$O(m+n)O(m+n)$O(m+n)，（然而它AC了）

倒序处理+数学性质

对于最后插队的人来说，不论他之前插了几次队，在什么位置，最终他会在队伍的最前面，同时他除了最后一次插队之前的动作对其他人位置的结果无影响。

那么把插队序列，倒过来看，也就是，同一个人的插队，只有最后一次是有效的。

对于没有插队的人，我们把最终的序列看成

[插队的人][连续的没有插队的人][连续的没有插队的人][连续的没有插队的人][连续的没有插队的人]

要求的是，位置不同的人，那么显然除了最后的连续的没有插队的人以外, 其它的连续的没有插队的人都是变了位置的

所以 答案 = 插队的人中位置变化的 + (插队的人的最大值-插队人的人数)，由此代码可以实现

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算有多少个人最终不在自己原来的位置上
     * @param n int整型 队伍总长
     * @param cutIn int整型vector 依次会插队到最前方的人的编号
     * @return int整型
     */
    int countDislocation(int n, vector<int>& cutIn) {
        if(cutIn.size() == 0)return 0;
        set<int> cutpset; // 防止重复
        vector<int> cutp; // 所有插队的人从小到大
        for(auto p:cutIn){
            if(cutpset.count(p))continue; // 放置重复
            cutpset.insert(p);
            cutp.push_back(p);
        }
        sort(cutp.begin(),cutp.end()); // 所有插队的人从小到大
      
        cutpset = {};// 清空 放置重复
        int ans = 0;
        int pos = 1;
        for(int i = cutIn.size()-1;i>=0;i--){
            int p = cutIn[i];
            if(cutpset.count(p))continue; // 插队多次以最后一次为准
            cutpset.insert(p);
            ans += p != pos; // 插队的人和初始位置不同
            pos++;
        }
        return ans + (cutp[cutp.size()-1] - cutp.size()); // 插队的人中位置变化的 + (插队的人的最大值-插队人的人数)
    }
};

复杂度分析

空间复杂度: 这里我们的空间，使用的是防重复set和排序的vector，都是存储插队的人的，所以复杂度为$O\left(m\right)O(m)$O(m)

时间复杂度: 我们所有循环都是在遍历了cutIn 数组。最初的统计插队的人，后面的比较插队的人的位置，每个具体计算都是常数代价。此外我们使用了sort进行排序，所以总时间复杂度为$O(m\cdot log(m\left)\right)O(m\backslash cdot\; log(m))$O(m⋅log(m))