2025-09-15：距离最小相等元素查询。用go语言，给出一个首尾相连的数组 nums 以及若干查询下标 queries。对于每个查询位置 p = queries[i]，需要在数组中找出另一个下标 q（q ≠ p 且 nums[q] = nums[p]），使得在环状数组上从 p 到 q 的步数最少；如果不存在这样的 q，则该查询的结果为 -1。要求返回一个与 queries 等长的结果数组 answer，answer[i] 即为第 i 个查询的最小环上距离。这里“环上距离”指两下标之差的最小环绕距离，等于 min(|p−q|, n−|p−q|)。

1 <= queries.length <= nums.length <= 100000。

1 <= nums[i] <= 1000000。

0 <= queries[i] < nums.length。

输入： 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）。

题目来自力扣3488。

分步骤描述过程

1. 预处理：记录每个值出现的位置

   • 创建一个映射（map）pos，键为数组中的值，值为一个列表，存储该值在数组 nums 中出现的所有索引（按索引从小到大自然有序）。
   • 遍历数组 nums，对于每个元素 nums[i]，将索引 i 添加到 pos[nums[i]] 对应的列表中。

2. 处理每个查询

   • 对于每个查询下标 queries[i]，记 p = queries[i]，目标值 target = nums[p]。
   • 在映射 pos 中查找 target 对应的位置列表 thelist。
     • 如果 thelist 的长度为 1（即该值只出现一次），则没有其他相同值的下标，结果设为 -1。
     • 否则，继续下一步。

3. 二分查找确定当前下标在列表中的位置

   • 使用二分查找（sort.SearchInts）确定 p 在 thelist 中的位置 ind（即第一个大于等于 p 的索引位置，相当于 bisect_left）。
   • 根据 ind 在列表中的位置分三种情况处理：
     • 情况1：ind 是列表的第一个元素（即 ind == 0）
       • 计算向右到下一个相同值的距离 d1 = thelist[1] - thelist[0]。
       • 计算向左（环状）到最后一个相同值的距离 d2 = n - thelist[listlen-1] + thelist[0]（因为数组是环状的，从首到尾需要绕回）。
       • 取 d1 和 d2 的最小值作为结果。
     • 情况2：ind 是列表的最后一个元素（即 ind == listlen-1）
       • 计算向左到上一个相同值的距离 d1 = thelist[listlen-1] - thelist[listlen-2]。
       • 计算向右（环状）到第一个相同值的距离 d2 = n + thelist[0] - thelist[listlen-1]（因为数组是环状的，从尾到首需要绕回）。
       • 取 d1 和 d2 的最小值作为结果。
     • 情况3：ind 在列表中间
       • 计算向右到下一个相同值的距离 d1 = thelist[ind+1] - thelist[ind]。
       • 计算向左到上一个相同值的距离 d2 = thelist[ind] - thelist[ind-1]。
       • 取 d1 和 d2 的最小值作为结果。

4. 返回结果数组

   • 将所有查询的结果存储在数组 ans 中并返回。

总的时间复杂度和总的额外空间复杂度

• 时间复杂度：

  • 预处理：遍历数组 nums 一次，时间复杂度为 O(n)。
  • 处理每个查询：对于每个查询，二分查找位置列表的时间为 O(log k)（其中 k 是相同值的出现次数），最坏情况下 k 可能达到 n（但每个值出现的次数不会太多，实际中平均较低），总查询数为 m（即 queries 的长度），因此总时间复杂度为 O(m log k)。由于 k 的最大值可能较大，但平均情况下较小，总体效率较高。
  • 总时间复杂度为 O(n + m log k)。

• 额外空间复杂度：

  • 映射 pos 存储每个值的位置列表，最坏情况下所有值都不同（但值可能重复，实际存储的索引总数等于 n），因此空间复杂度为 O(n)。
  • 结果数组 ans 长度为 m，空间复杂度为 O(m)。
  • 总额外空间复杂度为 O(n + m)。由于 n 和 m 同数量级（题目中 queries.length <= nums.length），可简化为 O(n)。

总结：该算法通过预处理记录每个值的位置，然后对每个查询使用二分查找快速定位最近邻，高效地解决了环状数组中最小距离查询问题。时间复杂度和空间复杂度均在合理范围内。

Go完整代码如下：

package main

import (
	"fmt"
	"sort"
)

func solveQueries(nums []int, queries []int) []int {
	n := len(nums)
	// 记录每个值出现的位置（已按索引自然有序）
	pos := make(map[int][]int)
	for i, v := range nums {
		pos[v] = append(pos[v], i)
	}

	ans := make([]int, len(queries))
	for i, q := range queries {
		target := nums[q]
		thelist := pos[target]
		if len(thelist) == 1 {
			ans[i] = -1
			continue
		}

		// 二分查找 q 在 thelist 中的位置（等价于 bisect_left）
		ind := sort.SearchInts(thelist, q)
		listlen := len(thelist)

		if ind == 0 {
			d1 := thelist[1] - thelist[0]
			d2 := n - thelist[listlen-1] + thelist[0]
			if d2 < d1 {
				ans[i] = d2
			} else {
				ans[i] = d1
			}
		} else if ind == listlen-1 {
			d1 := thelist[listlen-1] - thelist[listlen-2]
			d2 := n + thelist[0] - thelist[listlen-1]
			if d2 < d1 {
				ans[i] = d2
			} else {
				ans[i] = d1
			}
		} else {
			curr := thelist[ind]
			d1 := thelist[ind+1] - curr
			d2 := curr - thelist[ind-1]
			if d1 < d2 {
				ans[i] = d1
			} else {
				ans[i] = d2
			}
		}
	}

	return ans
}

func main() {
	nums := []int{1, 3, 1, 4, 1, 3, 2}
	queries := []int{0, 3, 5}
	result := solveQueries(nums, queries)
	fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

from bisect import bisect_left

def solve_queries(nums, queries):
    n = len(nums)
    # 记录每个值出现的位置（按索引自然有序）
    pos = {}
    for i, v in enumerate(nums):
        pos.setdefault(v, []).append(i)

    ans = [0] * len(queries)
    for i, q in enumerate(queries):
        target = nums[q]
        thelist = pos[target]
        if len(thelist) == 1:
            ans[i] = -1
            continue

        # 二分查找 q 在 thelist 中的位置（等价于 bisect_left）
        ind = bisect_left(thelist, q)
        listlen = len(thelist)

        if ind == 0:
            d1 = thelist[1] - thelist[0]
            d2 = n - thelist[-1] + thelist[0]
            ans[i] = d2 if d2 < d1 else d1
        elif ind == listlen - 1:
            d1 = thelist[-1] - thelist[-2]
            d2 = n + thelist[0] - thelist[-1]
            ans[i] = d2 if d2 < d1 else d1
        else:
            curr = thelist[ind]
            d1 = thelist[ind + 1] - curr
            d2 = curr - thelist[ind - 1]
            ans[i] = d1 if d1 < d2 else d2

    return ans

if __name__ == "__main__":
    nums = [1, 3, 1, 4, 1, 3, 2]
    queries = [0, 3, 5]
    print(solve_queries(nums, queries))