小美的排列询问
美团 2024 秋招笔试编程题
题目描述
小美拿到了一个排列。她想知道在这个排列中，数字 x 和 y 是否是相邻的。 排列是指一个长度为 n 的数组，其中 1 到 n 每个元素恰好出现一次。
输入格式
第一行一个正整数 n，代表排列的长度。 第二行 n 个正整数，代表排列的元素。 第三行两个正整数 x 和 y，用空格隔开。
输出格式
如果 x 和 y 在排列中相邻，输出 Yes；否则输出 No。
示例
示例 1
输入：
4
1 4 2 3
2 4
输出：
Yes
说明：
排列为 1 4 2 3，4 在第 2 位、2 在第 3 位，下标相差 1，相邻。
示例 2
输入：
5
3 4 5 1 2
3 2
输出：
No
说明：
3 在第 1 位、2 在第 5 位，下标相差 4，不相邻。
解题思路
第一步：把「相邻」翻译成下标条件
数组里「两个数相邻」只有一种含义：它们的位置下标相差 1。 所以问题变成：找出 x 和 y 各自出现的位置，判断下标差是否为 1。
第二步：暴力查找（不推荐）
每次都从头扫一遍数组找 x 和 y，单次查询 O(n)。 因为题目只问一次，暴力也能过，但没有体现出「排列」这个条件的好处。
第三步：值 → 下标 的映射（推荐）
排列的一个好处是每个值恰好出现一次，所以可以建一张表： 「值 → 在数组中的下标」。一次遍历把表建好，查询就是 O(1)：
abs(pos[x] - pos[y]) == 1 → Yes
Python 里用 dict，或者因为值域是 1..n，直接用长度为 n + 1 的数组更快。
完整代码实现
算法可视化 · 逐帧回放这道题的代码18 帧 · 录制输入
import sys
def solve() -> None:
"""记录每个值的位置，判断下标是否相差 1"""
data = sys.stdin.read().split()
if not data:
return
n = int(data[0])
a = data[1:1 + n]
x = data[1 + n]
y = data[2 + n]
pos = {}
for i, v in enumerate(a):
pos[v] = i
sys.stdout.write("Yes\n" if abs(pos[x] - pos[y]) == 1 else "No\n")
if __name__ == "__main__":
solve()
示例推演
以 n = 4, a = [1, 4, 2, 3], x = 2, y = 4 为例：
| 值 | 下标 |
|---|---|
| 1 | 0 |
| 4 | 1 |
| 2 | 2 |
| 3 | 3 |
|pos[2] - pos[4]| = |2 - 1| = 1 → 输出 Yes。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 每次线性查找 | O(n) | O(1) | 只问一次也能过 |
| 值 → 下标 映射 | O(n) | O(n) | 推荐，查询 O(1) |
易错点总结
1. 把「相邻」理解成数值相邻
题目说的是位置相邻，不是数值相差 1。
1 4 2 3 里 4 和 2 数值差 2，但位置相邻 → Yes。
2. 输出大小写
题目要求输出 Yes / No（首字母大写），不是 YES / NO。
3. 忘记 x 或 y 可能在末尾
用「值 → 下标」的映射就不会有边界问题； 如果用双指针找相邻对，要注意数组末尾。
扩展思考
- 若问的是「x 和 y 之间隔了几个数」，答案就是
|i - j| - 1。 - 排列的「值恰好出现一次」性质在环（首尾相邻）问题里要单独处理。