Medium

题目描述

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

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

  • 索引 queries[i] 处的元素与循环数组中任何其他索引 j 之间的最小距离，其中 nums[j] == nums[queries[i]]。如果不存在这样的索引，该查询的答案应为 -1。

返回一个与 queries 大小相同的数组 answer，其中 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

解题思路

解题思路

这是一个在循环数组中查找最近相等元素的问题。核心思路是利用哈希表和二分搜索来优化查找过程。

方法分析：

  1. 预处理阶段：使用哈希表记录每个值对应的所有索引位置，并保持索引有序（天然有序）
  2. 查询阶段：对每个查询索引，在对应值的索引列表中使用二分搜索找到最近的其他索引

关键点：

  • 循环数组的距离计算：两个索引 i 和 j 的最小距离为 min(|i-j|, n-|i-j|)
  • 对于每个查询索引，需要在相同值的索引列表中找到最近的邻居
  • 使用二分搜索在有序列表中定位查询索引的位置，然后检查前后相邻元素

算法步骤：

  1. 遍历数组，建立值到索引列表的映射
  2. 对每个查询：
    • 获取该位置的值对应的索引列表
    • 如果列表长度 ≤ 1，返回 -1
    • 使用二分搜索找到查询索引的位置
    • 检查前后相邻索引，计算最小循环距离

这种方法避免了暴力搜索，充分利用了预处理和二分搜索的优势。

代码实现

class Solution {
public:
    vector<int> solveQueries(vector<int>& nums, vector<int>& queries) {
        int n = nums.size();
        unordered_map<int, vector<int>> valueToIndices;
        
        // 建立值到索引列表的映射
        for (int i = 0; i < n; i++) {
            valueToIndices[nums[i]].push_back(i);
        }
        
        vector<int> result;
        
        for (int queryIdx : queries) {
            int value = nums[queryIdx];
            vector<int>& indices = valueToIndices[value];
            
            if (indices.size() <= 1) {
                result.push_back(-1);
                continue;
            }
            
            // 使用二分搜索找到查询索引的位置
            int pos = lower_bound(indices.begin(), indices.end(), queryIdx) - indices.begin();
            
            int minDist = INT_MAX;
            
            // 检查前一个索引
            if (pos > 0) {
                int prevIdx = indices[pos - 1];
                int dist = min(abs(queryIdx - prevIdx), n - abs(queryIdx - prevIdx));
                minDist = min(minDist, dist);
            }
            
            // 检查后一个索引
            if (pos < indices.size() - 1) {
                int nextIdx = indices[pos + 1];
                int dist = min(abs(queryIdx - nextIdx), n - abs(queryIdx - nextIdx));
                minDist = min(minDist, dist);
            }
            
            result.push_back(minDist == INT_MAX ? -1 : minDist);
        }
        
        return result;
    }
};

class Solution:
    def solveQueries(self, nums: List[int], queries: List[int]) -> List[int]:
        from collections import defaultdict
        import bisect
        
        n = len(nums)
        value_to_indices = defaultdict(list)
        
        # 建立值到索引列表的映射
        for i, val in enumerate(nums):
            value_to_indices[val].append(i)
        
        result = []
        
        for query_idx in queries:
            value = nums[query_idx]
            indices = value_to_indices[value]
            
            if len(indices) <= 1:
                result.append(-1)
                continue
            
            # 使用二分搜索找到查询索引的位置
            pos = bisect.bisect_left(indices, query_idx)
            
            min_dist = float('inf')
            
            # 检查前一个索引
            if pos > 0:
                prev_idx = indices[pos - 1]
                dist = min(abs(query_idx - prev_idx), n - abs(query_idx - prev_idx))
                min_dist = min(min_dist, dist)
            
            # 检查后一个索引
            if pos < len(indices) - 1:
                next_idx = indices[pos + 1]
                dist = min(abs(query_idx - next_idx), n - abs(query_idx - next_idx))
                min_dist = min(min_dist, dist)
            
            result.append(-1 if min_dist == float('inf') else min_dist)
        
        return result

public class Solution {
    public IList<int> SolveQueries(int[] nums, int[] queries) {
        int n = nums.Length;
        var valueToIndices = new Dictionary<int, List<int>>();
        
        // 建立值到索引列表的映射
        for (int i = 0; i < n; i++) {
            if (!valueToIndices.ContainsKey(nums[i])) {
                valueToIndices[nums[i]] = new List<int>();
            }
            valueToIndices[nums[i]].Add(i);
        }
        
        var result = new List<int>();
        
        foreach (int queryIdx in queries) {
            int value = nums[queryIdx];
            var indices = valueToIndices[value];
            
            if (indices.Count <= 1) {
                result.Add(-1);
                continue;
            }
            
            // 使用二分搜索找到查询索引的位置
            int pos = indices.BinarySearch(queryIdx);
            if (pos < 0) pos = ~pos;
            
            int minDist = int.MaxValue;
            
            // 检查前一个索引
            if (pos > 0) {
                int prevIdx = indices[pos - 1];
                int dist = Math.Min(Math.Abs(queryIdx - prevIdx), n - Math.Abs(queryIdx - prevIdx));
                minDist = Math.Min(minDist, dist);
            }
            
            // 检查后一个索引
            if (pos < indices.Count - 1) {
                int nextIdx = indices[pos + 1];
                int dist = Math.Min(Math.Abs(queryIdx - nextIdx), n - Math.Abs(queryIdx - nextIdx));
                minDist = Math.Min(minDist, dist);
            }
            
            result.Add(minDist == int.MaxValue ? -1 : minDist);
        }
        
        return result;
    }
}

var solveQueries = function(nums, queries) {
    const n = nums.length;
    const valueToIndices = new Map();
    
    // Group indices by their values
    for (let i = 0; i < n; i++) {
        if (!valueToIndices.has(nums[i])) {
            valueToIndices.set(nums[i], []);
        }
        valueToIndices.get(nums[i]).push(i);
    }
    
    const result = [];
    
    for (const queryIdx of queries) {
        const value = nums[queryIdx];
        const indices = valueToIndices.get(value);
        
        if (indices.length === 1) {
            result.push(-1);
            continue;
        }
        
        let minDist = Infinity;
        
        for (const idx of indices) {
            if (idx !== queryIdx) {
                // Calculate circular distance
                const dist1 = Math.abs(idx - queryIdx);
                const dist2 = n - dist1;
                const minCircularDist = Math.min(dist1, dist2);
                minDist = Math.min(minDist, minCircularDist);
            }
        }
        
        result.push(minDist);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n + q log k)，其中 n 为数组长度，q 为查询数量，k 为相同值的最大索引数量
空间复杂度O(n)，用于存储哈希表中的索引列表