2025-09-15：距离最小相等元素查询。用go语言，给出一个首尾相连的数组 nums 以及若干查询下标 queries。对于

福大大架构师每日一题

发布于 2025-12-18 11:33:19

1450

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]
        iflen(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
            }
        } elseif 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]
        iflen(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))