D.二分查找-进阶——3488. 距离最小相等元素查询
题目链接：3488. 距离最小相等元素查询（中等）
算法原理：
解法一：哈希表（会超时）
时间复杂度O(M×N)
哈希表存<值，此值出现的下标集合>
遍历queries，取到对应在nums中的值，如果没有取到本身这个下标，就取环形数组中距离此值最近的相同值的距离存进结果链表中
注：取环形链表的下标间的距离可以用Math.min(Math.abs(tmp-x), n-Math.abs(tmp-x))
解法二：二分查找
124ms击败74.20%
时间复杂度O(NLogN)
①预处理 —— 存储每个元素的所有原数组索引
遍历原数组nums，哈希表存<值，该值在原数组中的所有索引列表p>
特性：天然升序，为后续二分查找提供基础
②处理每个查询下标i
对每个查询的原数组下标i，依次执行以下操作：
特殊情况：p的长度为1时说明只有一个元素，直接添加-1
二分查找：i一定存在p中，所以一定能找到，最左端点和最右端点模型均可
prev = (left - 1 + k) % k：处理left=0时，前一个下标为p的最后一个下标（循环逻辑）
next = (left + 1) % k：处理left=k-1时，后一个下标为p的第一个下标（循环逻辑）
计算原数组环形最短距离：
结合原数组的环形特性，取「直接距离」和「原数组长度n - 直接距离」的最小值（即环形最短距离），得到disprev和disnext
结果存储：取disprev和disnext的最小值，添加到结果列表中
③返回结果
遍历完所有查询后，返回结果列表ret答疑
Q1：为什么p的下标可以用取模？
因为p记录的是nums中数的下标，而nums是环形数组
Q2：为什么 nums 的环形距离不能直接用取模？
取模只能确定下标，而解决不了有距离的路径最短的问题
Java代码：
class Solution { public List<Integer> solveQueries(int[] nums, int[] queries) { Map<Integer,List<Integer>> hash=new HashMap<>(); int n=nums.length; List<Integer> ret=new ArrayList<>(); for(int i=0;i<n;i++) hash.computeIfAbsent(nums[i],k->new ArrayList<>()).add(i); for(int x:queries){ int t=nums[x]; int mins=0x3f3f3f3f; List<Integer> a=hash.get(t); for(int tmp:a) if(x-tmp!=0) mins=Math.min(mins,Math.min(Math.abs(tmp-x), n-Math.abs(tmp-x))); if(mins==0x3f3f3f3f) mins=-1; ret.add(mins); } return ret; } }class Solution { public List<Integer> solveQueries(int[] nums, int[] queries) { Map<Integer,List<Integer>> hash=new HashMap<>(); int n=nums.length; List<Integer> ret=new ArrayList<>(); for(int i=0;i<n;i++) hash.computeIfAbsent(nums[i],k->new ArrayList<>()).add(i); for(int i:queries){ //i是nums的下标 List<Integer> p=hash.get(nums[i]); int k=p.size(); //这个元素只出现一次 if(k==1){ret.add(-1);continue;} //找到当前i在列表p中的位置 //由于当前索引一定在p中存在，所以用最左端点和最右端点的模型均可 int left=0,right=p.size()-1; while(left<right){ int mid=left+(right-left)/2; if(p.get(mid)<i) left=mid+1; else right=mid; } int prev=(left-1+k)%k; int next=(left+1)%k; //计算原数组索引的距离 int disprev = Math.min(Math.abs(i-p.get(prev)), n - Math.abs(i-p.get(prev))); // nums环形距离 int disnext = Math.min(Math.abs(i-p.get(next)), n - Math.abs(i-p.get(next))); // nums环形距离 ret.add(Math.min(disnext,disprev)); } return ret; } }