C - 排列的逆置 (Inverse of Permutation)

时间限制: 2 秒 内存限制: 1024 MiB 分值: 300 分

---

📖 题目描述

一个长度为 N 的序列，如果其中 1,2,…,N 每个数都恰好出现一次，则称它为一个 ​长度 N 的排列​。

现在给定一个排列：

P=(p1,p2,…,pN)请输出另一个排列：

Q=(q1,q2,…,qN)要求满足：

对于每个 ​i(1 ≤ i ≤ N)​，有

$Q[p\_i] = i$

可以证明，这样的 Q 存在且唯一。

---

📌 输入格式

N
p1 p2 … pN

• ​N​：排列长度
• ​p1 … pN​：给定的排列

---

📌 输出格式

q1 q2 … qN

输出排列 Q。

---

🔒 数据范围

• 1 ≤ N ≤ 2×10⁵
• (p1, …, pN) 是 {1,2,…,N} 的一个排列。

---

🎯 样例输入 1

3
2 3 1

🎯 样例输出 1

3 1 2

解释：

• i=1 → p1=2 → q2=1
• i=2 → p2=3 → q3=2
• i=3 → p3=1 → q1=3

---

🎯 样例输入 2

3
1 2 3

🎯 样例输出 2

1 2 3

此时 ​P = Q​。

---

🎯 样例输入 3

5
5 3 2 4 1

🎯 样例输出 3

5 3 2 4 1

---

💡 思路讲解

题目要求：

$Q[p\_i] = i$也就是说：

• P 中第 i 个数是 pᵢ
• 那么在 ​Q 的第 pᵢ 个位置​，应该放上 ​i​。

👉 换句话说，​Q 就是 P 的反向映射​。

---

---

✅ ​核心技巧总结​：

• 输入是一个 排列 P
• 输出它的 逆置 Q
• 利用关系 Q[pᵢ] = i 来直接构造。
• 时间复杂度 O(N)，空间 O(N)。

---