查询带键的排列

2021-02-05

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：

输入：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：

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

示例 3：

1 2	输入：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 int[] processQueries(int[] queries, int m) {
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            list.add(i + 1);
        }
        int[] res = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int index = list.indexOf(queries[i]);
            int val = list.remove(index);
            res[i] = index;
            list.add(0, val);
        }
        return res;
    }
}

模拟

class Solution {
    public int[] processQueries(int[] queries, int m) {
        List<Integer> p = new ArrayList<Integer>();
        for (int i = 1; i <= m; ++i) {
            p.add(i);
        }
        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; ++i) {
            int query = queries[i];
            int pos = -1;
            for (int j = 0; j < m; ++j) {
                if (p.get(j) == query) {
                    pos = j;
                    break;
                }
            }
            ans[i] = pos;
            p.remove(pos);
            p.add(0, query);
        }
        return ans;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/queries-on-a-permutation-with-key/solution/cha-xun-dai-jian-de-pai-lie-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

树状数组

对于每一个询问项 $\textit{query}$，我们想求出它在排列 $P$ 中的位置，实际上只要知道它的前面有几个数就可以了。由于排列 $P$ 的位置是从 $0 $开始的，因此这两者在数值上是等价的。

既然我们把这个问题的答案转化成了一个「数数」的过程，那么我们不妨再想想题目中的操作是不是也可以往「数数」的方向上靠。我们每次求出 $\textit{query}$ 之前有几个数之后，都需要把 $\textit{query}$ 移动到数组的首部，而这样是非常不优雅的。在方法一中，我们采用先从列表中「删除」这个数再将其「插入」数组首部的方法，导致时间复杂度为 $O(M)$。

但我们试想一下，如果在现实生活中，你要管理一个队伍，想把其中的一个人放到队首，你会怎么做？最简单的做法是直接把这个人拉出来让他/她站到第一个人的前面就行了。为什么我们可以这么做？这是因为现实生活中的队伍不是数组，在第一个人前面是有很多空间的。

这是否对我们的优化有一些借鉴的意义呢？我们知道查询的次数 $Q$，那么我们可以使用一个长度为 $Q + M$ 的数组，一开始的排列 $P$ 占据了数组的最后 $M$ 个位置，而每处理一个询问项 $\textit{query}$，我们将其直接放到数组的前 $Q$ 个位置就行了，顺序是从右往左放置。

以示例一为例，对于排列 [1, 2, 3, 4, 5] 以及查询 [3, 1, 2, 1]，一开始的数组为：

1	_ _ _ _ 1 2 3 4 5

前面空出了四个位置，即查询的长度。

我们第一次查询 $3$，$3$ 之前有 $2$ 个数。随后将 $3$ 移到前面：

1	_ _ _ 3 1 2 _ 4 5

我们第二次查询 $1$，$1$ 之前有 $1$ 个数。随后将 $1$ 移到前面：

1	_ _ 1 3 _ 2 _ 4 5

我们第二次查询 $2$，$1$ 之前有 $2$ 个数。随后将 $2$ 移到前面：

1	_ 2 1 3 _ _ _ 4 5

我们第二次查询 $1$，$1$ 之前有 $1$ 个数。随后将 $1$ 移到前面：

1	1 2 _ 3 _ _ _ 4 5

在上面的示例中，我们可以发现，我们只需要支持下面三个操作：

查询某一个位置之前有几个位置不为空，作为返回的答案；

将一个位置变为空；

将一个位置变为非空。

如果我们将「空」的位置看成 $1$，「非空」的位置看成 $0$，实际上就是要支持这些操作：

数组中一开始前 $Q$ 个位置为 $0$，后 $M$ 个位置为 $1$；

可以看成数组中一开始均为 $0$，我们使用 $M$ 次树状数组的单点修改操作，将对应的位置变为 $1$。
每次查询操作等价于询问一个前缀区间的和；

可以使用树状数组的区间查询操作。
将一个位置从 $1$ 变为 $0$；

可以使用树状数组的单点修改操作。
将一个位置从 $0$ 变为 $1$。

可以使用树状数组的单点修改操作。
这样就变成了一个可以用树状数组解决的问题了。

class Solution {
    public int[] processQueries(int[] queries, int m) {
        int n = queries.length;
        BIT bit = new BIT(m + n);
        
        int[] pos = new int[m + 1];
        for (int i = 1; i <= m; ++i) {
            // 修改query以适应树状数组
            pos[i] = n + i;
            // 从有元素的位置初始化树状数组
            bit.update(n + i, 1);
        }
        
        int[] ans = new int[n];
        for (int i = 0; i < n; ++i) {
            int cur = pos[queries[i]];
            // 将当前值更新为-1求逆序数
            bit.update(cur, -1);
            // 获取前面的数字的个数
            ans[i] = bit.query(cur);
            cur = n - i;
            pos[queries[i]] = cur;
            bit.update(cur, 1);
        }
        return ans;
    }
}

class BIT {
    int[] a;
    int n;

    public BIT(int n) {
        this.n = n;
        this.a = new int[n + 1];
    }

    public int query(int x) {
        int ret = 0;
        while (x != 0) {
            ret += a[x];
            x -= lowbit(x);
        }
        return ret;
    }

    public int update(int x, int dt) {
        while (x <= n) {
            a[x] += dt;
            x += lowbit(x);
        }
        return x;
    }

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

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/queries-on-a-permutation-with-key/solution/cha-xun-dai-jian-de-pai-lie-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。