第 478 场周赛Q3——3761. 镜像对之间最小绝对距离

题目链接3761. 镜像对之间最小绝对距离中等算法原理对应力扣题解解法哈希表54ms击败77.45%时间复杂度O(N)①使用哈希表既然要找两个数之间的距离那么可以把一个存进哈希表在遍历的时候判断两数之间能否匹配上从而更新距离②更新最后一次出现位置由于要求的是最小的绝对距离所以要更新把出现的位置更新到最后一次从而保证距离最小而不是最大③哈希表记录更早信息明确哈希表中存的是什么存的是数最后一次出现下标那么这个数是什么数呢答案是要存“在当前位置看来之前出现过的当前位置的数”也就是在当前位置的数看来是当前位置的数翻转过的数为什么不存原始数然后检查当前数翻转后是否等于原始数呢首先明确在当前位置看来之前出现过的当前位置的数的位置为i因为题目要求的是 reverse(nums[i]) nums[j]而咱们遍历的就是 j 如果存之前的原始数就会变成 nums[i]reverse(nums[j])正好与题意要求相反所以存进哈希表的是当前数翻转过的数④总结以上思路遍历数组直接用当前数当key,检查之前是否有翻转数key有的话就更新最小距离之后更新此数的翻转数的最后一次出现位置最后检查ret是否存了最小距离没存就代表没有符合题意的数直接返回-1Java代码class Solution { public int minMirrorPairDistance(int[] nums) { int nnums.length; int ret0x3f3f3f3f; //存数,最后一次出现下标 //哈希表记录更早的信息 MapInteger,Integer hashnew HashMap(); for(int j0;jn;j){ int curnums[j]; //直接用当前数当key,检查之前是否有翻转数key //如果把cur存进哈希表然后查找cur的翻转值就会变成 //nums[i]reverse(nums[j]) //与题目要求的reverse(nums[i]) nums[j]相反 //就是ij要成立所以记录更早信息要存cur的翻转值 if(hash.containsKey(cur)) retMath.min(ret,j-hash.get(cur)); hash.put(reverse(cur),j); } return ret0x3f3f3f3f?-1:ret; } private int reverse(int n){ int ret0; //自动去除了前导0 while(n!0){ int tn%10; retret*10t; n/10; } return ret; } }