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

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

通过示例1来分析：

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

对于queries[0] = 0, nums[queries[0]] = 1来说，其在nums中的下标集合为p = [0, 2, 4]，由于nums是一个循环数组，所以按理来说数组p的第一个元素往左需要能找到最后一个元素，最后一个元素往右能找到第一个元素。

n 为 nums 的长度，在下标列表前面添加 4−n=−3，相当于认为在 −3 下标处也有一个 1。在下标列表末尾添加 0+n=7，相当于认为在 7 下标处也有一个 1。

题意是需要我们查询一个 nums 中的下标 x，与任意其他下标 j（满足 nums[j] == nums[x]）之间的最小距离。我们用哈希表将每个相同值的元素的下标收集起来作为集合 p，然后在查询时使用二分查询 x 在其对应集合中的位置 i，则左边最近的元素下标为 p[i - 1]，右边最近元素下标为 p[i + 1]，那么最小距离就是 min(p[i + 1] - x, x - p[i - 1])。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    vector<int> solveQueries(vector<int>& nums, vector<int>& queries) {
        unordered_map<int, vector<int>> m;
        int n = nums.size();
        
        // 将每个相同值的元素的下标收集起来
        for (int i = 0; i < nums.size(); ++i) {
            m[nums[i]].push_back(i);
        }
        
        // 增加左右两个哨兵
        for (auto& [_, p] : m) {
            int t = p[0];
            p.insert(p.begin(), p.back() - n);
            p.push_back(n + t);
        }
        
        for (int& x : queries) {
            auto& p = m[nums[x]];
            if (p.size() == 3) {
	            // 由于添加了两个哨兵，所以当集合长度为 3 时说明集合中实际只有1个元素，即这个元素在 nums 中是唯一的
                x = -1;
            } else {
                int i = ranges::lower_bound(p, x) - p.begin();
                x = min(p[i + 1] - x, x - p[i - 1]);
            }
        }
        return queries;
    }
};