Medium

题目描述

给你一个由正整数组成的数组 nums。

如果两个整数 x 和 y 满足以下条件，我们称它们在这个问题中 几乎相等：

  • 两个整数都可以通过执行以下操作 至多一次 后变得相等：
    • 选择 x 或 y 中的一个，交换所选数字中的任意两个数位。

返回数组 nums 中满足 i < j 且 nums[i] 和 nums[j] 几乎相等的下标对 (i, j) 的数目。

注意，执行操作后整数可以有前导零。

示例 1：

输入：nums = [3,12,30,17,21]

输出：2

解释：

几乎相等的数对有：

  • 3 和 30。通过交换 30 中的 3 和 0，得到 3。
  • 12 和 21。通过交换 12 中的 1 和 2，得到 21。

示例 2：

输入：nums = [1,1,1,1,1]

输出：10

解释：

数组中的每两个元素都几乎相等。

示例 3：

输入：nums = [123,231]

输出：0

解释：

我们无法通过交换 123 或 231 的任意两个数位来使它们相等。

提示：

  • 2 <= nums.length <= 100
  • 1 <= nums[i] <= 10^6

解题思路

解题思路

这道题需要判断两个数字是否"几乎相等"，即通过对其中一个数字交换任意两位数字，能否使两个数字相等。

核心思路

  1. 暴力枚举：由于数组长度最多100，可以枚举所有数对 (i,j) 其中 i < j
  2. 几乎相等判断：对于每一对数字，需要判断是否满足几乎相等条件
  3. 交换操作模拟：对每个数字尝试所有可能的两位数字交换，看是否能得到另一个数字

判断几乎相等的方法

对于两个数字 a 和 b，我们需要：

  1. 先检查它们是否已经相等
  2. 如果不相等，尝试对 a 进行所有可能的两位交换，看能否得到 b
  3. 如果还不行，尝试对 b 进行所有可能的两位交换，看能否得到 a

实现细节

  • 将数字转换为字符串便于操作各个数位
  • 对于每个数字，枚举所有可能的两位交换组合
  • 交换后转回数字进行比较

时间复杂度：O(n² × d²)，其中 n 是数组长度，d 是数字的位数（最多7位） 空间复杂度：O(d)，用于存储数字的字符串表示

代码实现

class Solution {
public:
    int countPairs(vector<int>& nums) {
        int n = nums.size();
        int count = 0;
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (areAlmostEqual(nums[i], nums[j])) {
                    count++;
                }
            }
        }
        
        return count;
    }
    
private:
    bool areAlmostEqual(int a, int b) {
        if (a == b) return true;
        
        // Try swapping digits in a
        if (canMakeEqual(a, b)) return true;
        
        // Try swapping digits in b
        if (canMakeEqual(b, a)) return true;
        
        return false;
    }
    
    bool canMakeEqual(int num, int target) {
        string s = to_string(num);
        int len = s.length();
        
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                swap(s[i], s[j]);
                if (stoi(s) == target) {
                    return true;
                }
                swap(s[i], s[j]); // swap back
            }
        }
        
        return false;
    }
};

class Solution:
    def countPairs(self, nums: List[int]) -> int:
        def can_make_equal(num, target):
            s = list(str(num))
            n = len(s)
            
            for i in range(n):
                for j in range(i + 1, n):
                    s[i], s[j] = s[j], s[i]
                    if int(''.join(s)) == target:
                        return True
                    s[i], s[j] = s[j], s[i]  # swap back
            
            return False
        
        def are_almost_equal(a, b):
            if a == b:
                return True
            
            # Try swapping digits in a
            if can_make_equal(a, b):
                return True
            
            # Try swapping digits in b
            if can_make_equal(b, a):
                return True
            
            return False
        
        n = len(nums)
        count = 0
        
        for i in range(n):
            for j in range(i + 1, n):
                if are_almost_equal(nums[i], nums[j]):
                    count += 1
        
        return count

public class Solution {
    public int CountPairs(int[] nums) {
        int n = nums.Length;
        int count = 0;
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (AreAlmostEqual(nums[i], nums[j])) {
                    count++;
                }
            }
        }
        
        return count;
    }
    
    private bool AreAlmostEqual(int a, int b) {
        if (a == b) return true;
        
        // Try swapping digits in a
        if (CanMakeEqual(a, b)) return true;
        
        // Try swapping digits in b
        if (CanMakeEqual(b, a)) return true;
        
        return false;
    }
    
    private bool CanMakeEqual(int num, int target) {
        char[] chars = num.ToString().ToCharArray();
        int len = chars.Length;
        
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                // Swap
                char temp = chars[i];
                chars[i] = chars[j];
                chars[j] = temp;
                
                if (int.Parse(new string(chars)) == target) {
                    return true;
                }
                
                // Swap back
                temp = chars[i];
                chars[i] = chars[j];
                chars[j] = temp;
            }
        }
        
        return false;
    }
}

var countPairs = function(nums) {
    function areAlmostEqual(x, y) {
        let s1 = x.toString();
        let s2 = y.toString();
        
        // Pad shorter string with leading zeros
        let maxLen = Math.max(s1.length, s2.length);
        s1 = s1.padStart(maxLen, '0');
        s2 = s2.padStart(maxLen, '0');
        
        let diff = [];
        for (let i = 0; i < maxLen; i++) {
            if (s1[i] !== s2[i]) {
                diff.push(i);
            }
        }
        
        if (diff.length === 0) return true;
        if (diff.length === 2) {
            return (s1[diff[0]] === s2[diff[1]] && s1[diff[1]] === s2[diff[0]]);
        }
        
        // Check if we can make them equal by swapping digits in s1
        let chars1 = s1.split('');
        for (let i = 0; i < maxLen; i++) {
            for (let j = i + 1; j < maxLen; j++) {
                [chars1[i], chars1[j]] = [chars1[j], chars1[i]];
                if (chars1.join('') === s2) return true;
                [chars1[i], chars1[j]] = [chars1[j], chars1[i]];
            }
        }
        
        // Check if we can make them equal by swapping digits in s2
        let chars2 = s2.split('');
        for (let i = 0; i < maxLen; i++) {
            for (let j = i + 1; j < maxLen; j++) {
                [chars2[i], chars2[j]] = [chars2[j], chars2[i]];
                if (chars2.join('') === s1) return true;
                [chars2[i], chars2[j]] = [chars2[j], chars2[i]];
            }
        }
        
        return false;
    }
    
    let count = 0;
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (areAlmostEqual(nums[i], nums[j])) {
                count++;
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n² × d²)n为数组长度，d为数字最大位数(≤7)，需要枚举所有数对，每对需要尝试所有可能的数位交换
空间复杂度O(d)需要额外空间存储数字的字符串表示

相关题目