Medium

题目描述

给你一个整数数组 nums。

镜像对是指满足以下条件的一对索引 (i, j)：

  • 0 <= i < j < nums.length，且
  • reverse(nums[i]) == nums[j]，其中 reverse(x) 表示将 x 的数字反转后形成的整数。反转后会省略前导零，例如 reverse(120) = 21。

返回任意镜像对索引之间的最小绝对距离。索引 i 和 j 之间的绝对距离是 abs(i - j)。

如果不存在镜像对，返回 -1。

示例 1：

输入：nums = [12,21,45,33,54]
输出：1
解释：
镜像对包括：
- (0, 1)，因为 reverse(nums[0]) = reverse(12) = 21 = nums[1]，绝对距离为 abs(0 - 1) = 1。
- (2, 4)，因为 reverse(nums[2]) = reverse(45) = 54 = nums[4]，绝对距离为 abs(2 - 4) = 2。
所有对中的最小绝对距离是 1。

示例 2：

输入：nums = [120,21]
输出：1
解释：
只有一个镜像对 (0, 1)，因为 reverse(nums[0]) = reverse(120) = 21 = nums[1]。
最小绝对距离是 1。

示例 3：

输入：nums = [21,120]
输出：-1
解释：
数组中没有镜像对。

约束条件：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9

解题思路

解题思路

这道题要求找到镜像对之间的最小距离。关键在于理解镜像对的定义：一个数字的反转等于另一个数字。

核心思路：

  1. 我们需要找到满足 reverse(nums[i]) == nums[j] 且 i < j 的索引对
  2. 为了找到最小距离，我们应该尽早发现匹配
  3. 使用哈希表记录每个数字的反转值对应的最新索引位置

算法步骤：

  1. 从左到右遍历数组
  2. 对于每个 nums[i]，检查哈希表中是否存在键 nums[i]（即之前是否有数字的反转值等于当前数字）
  3. 如果存在，计算距离并更新最小值
  4. 将当前数字的反转值作为键，当前索引作为值存入哈希表

为什么要存储反转值：

  • 当我们遍历到位置 j 的数字时，我们希望找到之前位置 i 的数字满足 reverse(nums[i]) == nums[j]
  • 因此我们在位置 i 时存储 reverse(nums[i]) 到索引 i 的映射
  • 这样在位置 j 时就可以直接查找 nums[j] 是否在哈希表中

这种方法只需要一次遍历，时间复杂度为 O(n log m)，其中 m 是数字的最大值。

代码实现

class Solution {
public:
    int reverse(int num) {
        int result = 0;
        while (num > 0) {
            result = result * 10 + num % 10;
            num /= 10;
        }
        return result;
    }
    
    int minMirrorPairDistance(vector<int>& nums) {
        unordered_map<int, int> reversedMap;
        int minDist = INT_MAX;
        
        for (int i = 0; i < nums.size(); i++) {
            if (reversedMap.count(nums[i])) {
                minDist = min(minDist, i - reversedMap[nums[i]]);
            }
            reversedMap[reverse(nums[i])] = i;
        }
        
        return minDist == INT_MAX ? -1 : minDist;
    }
};

class Solution:
    def minMirrorPairDistance(self, nums: List[int]) -> int:
        def reverse_num(num):
            result = 0
            while num > 0:
                result = result * 10 + num % 10
                num //= 10
            return result
        
        reversed_map = {}
        min_dist = float('inf')
        
        for i, num in enumerate(nums):
            if num in reversed_map:
                min_dist = min(min_dist, i - reversed_map[num])
            reversed_map[reverse_num(num)] = i
        
        return min_dist if min_dist != float('inf') else -1

public class Solution {
    private int ReverseNumber(int num) {
        int result = 0;
        while (num > 0) {
            result = result * 10 + num % 10;
            num /= 10;
        }
        return result;
    }
    
    public int MinMirrorPairDistance(int[] nums) {
        Dictionary<int, int> reversedMap = new Dictionary<int, int>();
        int minDist = int.MaxValue;
        
        for (int i = 0; i < nums.Length; i++) {
            if (reversedMap.ContainsKey(nums[i])) {
                minDist = Math.Min(minDist, i - reversedMap[nums[i]]);
            }
            reversedMap[ReverseNumber(nums[i])] = i;
        }
        
        return minDist == int.MaxValue ? -1 : minDist;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var minMirrorPairDistance = function(nums) {
    function reverse(num) {
        return parseInt(num.toString().split('').reverse().join(''));
    }
    
    let minDistance = Infinity;
    
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (reverse(nums[i]) === nums[j]) {
                minDistance = Math.min(minDistance, j - i);
            }
        }
    }
    
    return minDistance === Infinity ? -1 : minDistance;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log m)n 为数组长度，m 为数字最大值，反转数字需要 O(log m) 时间
空间复杂度O(n)哈希表最多存储 n 个元素