---

1409. 查询带键的排列

• 标签：树状数组、数组、模拟
• 难度：中等

题目链接

• 1409. 查询带键的排列 - 力扣

题目大意

描述：给定一个正整数 $m$ 和一个查询数组 $queries$。初始数组 $P = [1, 2, \dots, m]$。对于每个查询 $q = queries[i]$：

1. 找到 $q$ 在 $P$ 中的位置 $pos$。
2. 将 $q$ 移到 $P$ 的开头，其余元素相对顺序右移。

要求：返回每个查询的位置 $pos$ 列表。

说明：

• $1 \le m \le 1000$。
• $1 \le queries.length \le 1000$。

示例：

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

解题思路

思路 1：模拟

1. 核心思想

$m \le 1000$，可以直接模拟数组操作。

2. 具体步骤

第 1 步：初始化 $P = [1, 2, \dots, m]$。

第 2 步：遍历 $queries$：

• 找到 $q$ 在 $P$ 中的索引 $pos$。
• 将 $P[pos]$ 从列表中删除，插入到列表开头。
• 记录 $pos$。

第 3 步：返回 $pos$ 列表。

3. 举例说明

以 $m=5, queries=[3,1,2,1]$ 为例：

• 初始 $P=[1,2,3,4,5]$
• 查询 $3$：$pos=2$，移动后 $P=[3,1,2,4,5]$
• 查询 $1$：$pos=1$，移动后 $P=[1,3,2,4,5]$
• 查询 $2$：$pos=2$，移动后 $P=[2,1,3,4,5]$
• 查询 $1$：$pos=1$，移动后 $P=[1,2,3,4,5]$

结果：$[2,1,2,1]$。

思路 1：代码

class Solution:
    def processQueries(self, queries: List[int], m: int) -> List[int]:
        P = list(range(1, m + 1))
        ans = []
        for q in queries:
            pos = P.index(q)
            ans.append(pos)
            P.pop(pos)
            P.insert(0, q)
        return ans

思路 1：复杂度分析

• 时间复杂度：$O(n \times m)$，$n$ 是查询数，每次查找和删除 $O(m)$。$m \le 1000$，可行。
• 空间复杂度：$O(m)$。

---

思路 2：树状数组优化

如果 $m$ 很大，可以用树状数组维护每个元素的位置，将复杂度降至 $O(n \log m)$。本题 $m$ 较小，模拟即可。