3488.距离最小相等元素查询

Binary search，https://leetcode.cn/problems/closest-equal-element-queries/

给你一个循环数组 nums 和一个数组 queries 。

对于每个查询 i ，你需要找到以下内容：

数组 nums 中下标 queries[i] 处的元素与任意其他下标 j（满足 nums[j] == nums[queries[i]]）之间的最小距离。如果不存在这样的下标 j，则该查询的结果为 -1 。

返回一个数组 answer，其大小与 queries 相同，其中 answer[i] 表示查询i的结果。

示例 1：

输入： nums = [1,3,1,4,1,3,2], queries = [0,3,5]

输出： [2,-1,3]

解释：

查询 0：下标 queries[0] = 0 处的元素为 nums[0] = 1 。最近的相同值下标为 2，距离为 2。
查询 1：下标 queries[1] = 3 处的元素为 nums[3] = 4 。不存在其他包含值 4 的下标，因此结果为 -1。
查询 2：下标 queries[2] = 5 处的元素为 nums[5] = 3 。最近的相同值下标为 1，距离为 3（沿着循环路径：5 -> 6 -> 0 -> 1）。

示例 2：

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

输出： [-1,-1,-1,-1]

解释：

数组 nums 中的每个值都是唯一的，因此没有下标与查询的元素值相同。所有查询的结果均为 -1。

提示：

1 <= queries.length <= nums.length <= 10^5
1 <= nums[i] <= 10^6
0 <= queries[i] < nums.length

python

from typing import List
from collections import defaultdict
import bisect

class Solution:
    def solveQueries(self, nums: List[int], queries: List[int]) -> List[int]:
        n = len(nums)

        def min_circular_distance(a, b, n):
            diff = abs(a - b)
            return min(diff, n - diff)

        # Build a mapping from value to all its indices (sorted)
        indices = defaultdict(list)
        for i, num in enumerate(nums):
            indices[num].append(i)

        # for num in indices:
        #     indices[num].sort()


        answer = []
        for idx in queries:
            value = nums[idx]
            pos_list = indices[value]

            # If there's only one occurrence, no valid index exists.
            if len(pos_list) == 1:
                answer.append(-1)
                continue

            # Find the position of idx in the sorted list using binary search.
            pos = bisect.bisect_left(pos_list, idx)

            # Since the array is circular, check both left and right neighbors.
            # Using modulo to wrap around.
            left_neighbor = pos_list[(pos - 1) % len(pos_list)]
            right_neighbor = pos_list[(pos + 1) % len(pos_list)]

            # Compute circular distances.
            dist_left = min_circular_distance(idx, left_neighbor, n)
            dist_right = min_circular_distance(idx, right_neighbor, n)

            answer.append(min(dist_left, dist_right))
        return answer

if __name__ == "__main__":
    sol = Solution()
    #print(sol.solveQueries([2, 10, 20, 20, 20], [1, 4, 2]))  # [-1, -1, 1]
    print(sol.solveQueries([14,14,4,2,19,19,14,19,14], [2,4,8,6,3])) # [0,0,0,0]

要解决这个问题，我们需要在环形数组中找到与查询下标处的元素相同的其他下标，并计算最小距离。

核心思路

距离定义：在一个长度为 $n$ 的环形数组中，下标 $i$ 和 $j$ 之间的距离定义为 $min (| i - j |, n - | i - j |)$ 。这本质上是顺时针方向和逆时针方向距离的最小值。
寻找最近相同元素：
- 对于某个值 $v$ ，假设它出现在下标列表 $p_{0}, p_{1}, \dots, p_{k - 1}$ （已按升序排列）中。
- 如果该值只出现一次（ $k = 1$ ），则不存在其他相同元素，结果为 $- 1$ 。
- 如果出现多次（ $k \geq 2$ ），对于任意一个下标 $p_{i}$ ，其“最近”的相同元素必定是它在有序列表中的前驱（逆时针方向最邻近）或后继（顺时针方向最邻近）。
预处理 gaps（间距）：
- 相邻下标间的顺时针距离为 $g_{i} = p_{i + 1} - p_{i}$ （其中 $0 \leq i < k - 1$ ）。
- 最后一个下标回到第一个下标的环形顺时针距离为 $g_{k - 1} = n - (p_{k - 1} - p_{0})$ 。
- 对于下标 $p_{i}$ ，其顺时针到下一个元素的距离是 $g_{i}$ ，逆时针到上一个元素的距离是 $g_{i - 1}$ （循环处理，即 $g_{- 1} = g_{k - 1}$ ）。
- 下标 $p_{i}$ 的最小距离即为 $min (g_{i}, g_{i - 1})$ 。

算法步骤

遍历数组 nums，用哈希表（或数组，因为值域到 $10^{6}$ ）记录每个数值出现的所有下标。由于是按顺序遍历，记录的下标列表天然有序。
遍历哈希表：
- 跳过只出现一次的数值。
- 计算该数值所有下标之间的 $k$ 个间距。
- 计算每个下标对应的最小距离并存入预处理结果数组 res_at_idx。
遍历 queries，从 res_at_idx 中直接获取答案并返回。

Python 代码实现

python

from collections import defaultdict
from typing import List

class Solution:
    def solveQueries(self, nums: List[int], queries: List[int]) -> List[int]:
        n = len(nums)
        # 1. 记录每个数值出现的所有下标
        pos = defaultdict(list)
        for i, val in enumerate(nums):
            pos[val].append(i)
        
        # 2. 预处理每个下标对应的最小距离，初始化为 -1
        res_at_idx = [-1] * n
        
        for val, indices in pos.items():
            k = len(indices)
            if k < 2:
                continue
            
            # 3. 计算相邻下标之间的顺时针间距
            # indices 已经是升序的
            gaps = []
            for i in range(k - 1):
                gaps.append(indices[i+1] - indices[i])
            # 环形闭合处的间距：从最后一个下标顺时针绕回第一个下标
            gaps.append(n - (indices[-1] - indices[0]))
            
            # 4. 对于每一个下标，其最近距离是相邻两个间距的最小值
            for i in range(k):
                # indices[i] 的顺时针距离是 gaps[i]
                # indices[i] 的逆时针距离是 gaps[i-1] (Python 支持负索引，gaps[-1] 即最后一个间距)
                res_at_idx[indices[i]] = min(gaps[i], gaps[i-1])
        
        # 5. 根据查询下标返回结果
        return [res_at_idx[q] for q in queries]

复杂度分析

时间复杂度： $O (N + M)$ ，其中 $N$ 是数组 nums 的长度， $M$ 是 queries 的长度。
- 建立哈希表需要 $O (N)$ 。
- 计算所有间距的总次数等于所有数值出现的总次数，即 $O (N)$ 。
- 构造查询结果需要 $O (M)$ 。
空间复杂度： $O (N)$ 。我们需要存储每个下标的索引位置和预处理后的结果数组。

3488.距离最小相等元素查询 ​

3488.距离最小相等元素查询