题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给两个整数数组，把一个数组中的各个数字作为目标下标，求每个目标下标在另一个数组（循环数组）对应数字左右侧与自己最相近的同值元素距离（没有则取-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>> rec;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            rec[nums[i]].push_back(i);
        }
        for (auto &[_, v] : rec) {
            v.insert(v.begin(), v.back()-n); // 上一个循环最后一个
            v.push_back(v[1] + n); // 下一个循环第一个
        }
        // for (auto &p : rec) {
        //     cout << p.first << ":" << endl;
        //     for (int &i: p.second) {
        //         cout << i << " ";
        //     }
        //     cout << endl;
        // }
        for (int &i : queries) {
            auto &v = rec[nums[i]];
            if (v.size()==3) i = -1;
            else {
                int index = ranges::lower_bound(v, i)-v.begin();
                //cout << i << " " << index << endl;
                i = min(i - v[index - 1], v[index + 1] - i);
            }  
        }
        return queries;
    }
};