LeetCode 1409.查询带键的排列

给定一个正整数数组 queries ，其取值范围在 1 到 m 之间。 请你根据以下规则按顺序处理所有 queries[i]（从 i=0 到 i=queries.length-1）：

首先，你有一个排列 P=[1,2,3,…,m]。
对于当前的 i ，找到 queries[i] 在排列 P 中的位置（从 0 开始索引），然后将它移到排列 P 的开头（即下标为 0 处）。注意， queries[i] 的查询结果是 queries[i] 在 P 中移动前的位置。
返回一个数组，包含从给定 queries 中查询到的结果。

示例 1：

输入：queries = [3,1,2,1], m = 5
输出：[2,1,2,1]
解释：处理 queries 的过程如下：
对于 i=0: queries[i]=3, P=[1,2,3,4,5], 3 在 P 中的位置是 2，然后我们把 3 移动到 P 的开头，得到 P=[3,1,2,4,5] 。
对于 i=1: queries[i]=1, P=[3,1,2,4,5], 1 在 P 中的位置是 1，然后我们把 1 移动到 P 的开头，得到 P=[1,3,2,4,5] 。
对于 i=2: queries[i]=2, P=[1,3,2,4,5], 2 在 P 中的位置是 2，然后我们把 2 移动到 P 的开头，得到 P=[2,1,3,4,5] 。
对于 i=3: queries[i]=1, P=[2,1,3,4,5], 1 在 P 中的位置是 1，然后我们把 1 移动到 P 的开头，得到 P=[1,2,3,4,5] 。
因此，包含结果的数组为 [2,1,2,1] 。
示例 2：

输入：queries = [4,1,2,2], m = 4
输出：[3,1,2,0]
示例 3：

输入：queries = [7,5,5,8,3], m = 8
输出：[6,5,0,7,5]

提示：

1 <= m <= 10^3
1 <= queries.length <= m
1 <= queries[i] <= m

法一：直接模拟：

class Solution {
public:
    vector<int> processQueries(vector<int>& queries, int m) {
        vector<int> P;
        for (int i = 1; i <= m; ++i)
        {
            P.push_back(i);
        }

        vector<int> ans;
        for (int query : queries)
        {
            int index = 0;
            for (; index < m; ++index)
            {
                if (P[index] == query)
                {
                    break;
                }
            }

            for (int i = index; i >= 1; --i)
            {
                P[i] = P[i - 1];
            }
            P[0] = query;
            ans.push_back(index);
        }

        return ans;
    }
};

如果queries的长度为n，此算法时间复杂度为O(nm)，空间复杂度为O(m)。

法二：树状数组，假如m为3，当要查询的数字为2时，相当于记下2前面有几个数后，把2放到m的最前面，因此，我们可以创建一个大小为查询数量加上m的数组，每当遍历到一个数字，我们需要统计它前面有几个数字，然后把它放到当前第一个数字的前面位置即可，统计前面有几个数可转换为求前缀和，有数字的位置值为1，没有数字时值为0，这就可以用树状数组求前缀和了：

class Solution {
public:
    vector<int> processQueries(vector<int>& queries, int m) {
        int queryNum = queries.size();
        array.resize(m + queryNum + 1);
        pos.resize(m + queryNum + 1);
        for (int i = 1; i <= m; ++i)
        {
            update(queryNum + i, 1);
            pos[i] = queryNum + i;
        }

        vector<int> ans;
        for (int i = 0; i < queryNum; ++i)
        {
            int queryTarget = queries[i];
            int targetPos = pos[queryTarget];
            // 统计前面有几个数字时，要去掉自己
            int res = query(targetPos) - 1;
            ans.push_back(res);
            // 把当前位置的数字设为不存在
            update(targetPos, -1);
            // 把当前位置的数字放到最前面数字的前一个位置
            // 根据遍历次数一个一个往前放即可
            pos[queryTarget] = queryNum - i;
            update(pos[queryTarget], 1);
        }

        return ans;
    }

private:
    vector<int> array;
    vector<int> pos;

    int lowbit(int x)
    {
        return x & -x;
    }

    int query(int x)
    {
        int ans = 0;
        while (x > 0)
        {
            ans += array[x];
            x -= lowbit(x);
        }

        return ans;
    }

    void update(int x, int diff)
    {
        while (x < array.size())
        {
            array[x] += diff;
            x += lowbit(x);
        }
    }
};

如果queries的长度为n，此算法时间复杂度为O(nlog(m+n))，空间复杂度为O(m+n)。