给定一个长度为 n、仅由数字 1、2、3 组成的数组，进行 q 轮查询。每轮给出位置 x 和数字 k（k 为 1/2/3 之一），要求找到数组中值为 k 且与 x 距离（按下标差的绝对值）最近的下标。请设计一个预处理后查询时间复杂度低于 O(qn) 的算法。
考察说明
考察离线/在线查询预处理、二分查找与复杂度分析能力
回答思路
- 能明确预处理时间与查询时间的关系
- 为每个数字分别存储其出现下标的有序列表
- 能在每个列表上用二分查找找最近下标
- 能正确比较左右两侧候选的距离并处理边界
- 能给出整体时间复杂度并解释为何低于 O(qn)
本题已收录答题指导
本题附完整参考答案与评分标准
登录后可查看结构化答题指导；也可以直接开一场模拟面试，AI 面试官用本题实时追问并给出评分。