力扣1409-查询带键的排列

摘要: 很难想到是树状数组

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

本文看一个维护数组上的操作的问题，直接模拟的方法比较好想，树状数组的做法很巧妙，非常难想。本题是第 184 场周赛 B 题。

---

$1 题目

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] 在 P 中的位置就是 queries[i] 的查询结果。

请你以数组形式返回待查数组 queries 的查询结果。

提示：

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

示例 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]

$2 题解

算法1: 模拟

按操作流程模拟即可，模拟的过程可以用数组也可以用链表。

一共 $O(Q)$ 次查询，每次查询需要 $O(M)$ 时间处理查找+移动，总时间复杂度 $O(MQ)$。

代码(C++) 数组模拟

class Solution {
public:
    vector<int> processQueries(vector<int>& queries, int m) {
        int Q = queries.size();
        vector<int> vec(m);
        for(int i = 0; i < m; ++i)
            vec[i] = i + 1;
        vector<int> result(Q);
        for(int i = 0; i < Q; ++i)
        {
            for(int j = 0; j < m; ++j)
                if(vec[j] == queries[i])
                {
                    result[i] = j;
                    vec.erase(vec.begin() + j);
                    vec.insert(vec.begin(), queries[i]);
                    break;
                }
        }
        return result;
    }
};

代码(C++) 链表模拟

class Solution {
public:
    vector<int> processQueries(vector<int>& queries, int m) {
        int Q = queries.size();
        list<int> l(m);
        int x = 1;
        for(auto it = l.begin(); it != l.end(); ++it)
            *it = x++;
        vector<int> result(Q);
        for(int i = 0; i < Q; ++i)
        {
            auto it = l.begin();
            int idx = 0;
            while(it != l.end())
            {
                if(*it == queries[i])
                {
                    result[i] = idx;
                    l.erase(it);
                    l.push_front(queries[i]);
                    break;
                }
                ++idx;2
                ++it;
            }
        }
        return result;
    }
};

算法2: 树状数组

对每个 j = query[i]，要求 result[i]，只需要知道当前的排列中 j 的前面有几个数。

初始时，vec 中是 1,2,…,m 排好的序列，一共对 vec 有 Q 次操作，每次操作都要取一个数放到前面。

可以一次性把这 Q 次操作的空间开出来，操作时直接将元素赋值给已经开出的空间，不影响已经持有元素的节点，因此可以避免移动。

维护操作

开长度为 m + Q 的数组维护操作，初始时，vec 为 [0,0,...,0,1,2,...,m]，即 Q 个 0 跟上 1,2,…,m。

操作 j = queries[i] 完成后，会将 j 从原有位置放到 vec[Q - 1 - i]。高效维护这个操作需要维护一个 mapping，mapping[j] 为 j 当前在 vec 的下标。

查询

此外在将 j 移动之前需要查询 [0..mapping[j]-1] 之前有多少个数，记为 c。则 result[i] = c。

高效维护查询可以用树状数组，[0..m+Q-1] 范围，有数字的记为 1，没数字的记为 0，查询 [0..mapping[j]-1] 之前有多少个数也就是查询 [0..mapping[j]-1] 的和。

代码 (C++)

class BIT
{
public:
    BIT(int n)
    {
        vec.assign(n + 1, 0);
        this -> n = n;
    }

    void add(int idx, int delta)
    {
        // vec[idx + 1] 增加 delta
        for(int i = idx + 1; i <= n; i += lowbit(i))
            vec[i] += delta;
    }

    int query(int idx)
    {
        // vec[1..idx+1] 的和
        int ans = 0;
        for(int i = idx + 1; i >= 1; i -= lowbit(i))
            ans += vec[i];
        return ans;
    }

private:
    vector<int> vec;
    int n;

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

class Solution {
public:
    vector<int> processQueries(vector<int>& queries, int m) {
        int Q = queries.size();
        // 维护操作
        // 初始时 [0,...,0,1,2,...,m]
        vector<int> vec(Q + m);
        // mapping[j] := j 在 vec 中的下标
        vector<int> mapping(m + 1);
        BIT bit(Q + m);
        for(int i = 0; i < m; ++i)
        {
            vec[Q + i] = i + 1;
            mapping[i + 1] = Q + i;
            bit.add(Q + i, 1);
        }
        vector<int> result(Q);
        for(int i = 0; i < Q; ++i)
        {
            int j = queries[i];
            int idx = mapping[j];
            result[i] = bit.query(idx - 1);
            vec[idx] = 0;
            vec[Q - 1 - i] = j;
            mapping[j] = Q - 1 - i;
            bit.add(idx, -1);
            bit.add(Q - 1 - i, 1);
        }
        return result;
    }
};

---