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]

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

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