Medium

题目描述

给你一个由正整数组成的数组 nums，其中所有整数都有相同的位数。

两个整数的数位差是指在相同位置上不同数字的个数。

返回 nums 中所有整数对的数位差之和。

示例 1：

输入: nums = [13,23,12]
输出: 4
解释:
我们有以下情况：
- 13 和 23 的数位差为 1
- 13 和 12 的数位差为 1  
- 23 和 12 的数位差为 2
所以所有整数对的数位差总和为 1 + 1 + 2 = 4

示例 2：

输入: nums = [10,10,10,10]
输出: 0
解释:
数组中所有整数都相同，所以所有整数对的数位差总和为 0

约束条件：

  • 2 <= nums.length <= 10^5
  • 1 <= nums[i] < 10^9
  • nums 中所有整数都有相同的位数

提示：

  • 你可以分别解决相同位置上的数字问题，然后将所有答案相加
  • 对于每个位置，统计从 0 到 9 每个数字在该位置出现的次数
  • 设 c 为某个数字在某个位置出现的次数，它对最终答案的贡献为 c * (n - c)，其中 n 是 nums 中整数的个数

解题思路

解题思路

这道题的核心思想是将问题拆分为每个数位位置独立计算，然后求和。

基本分析： 如果暴力枚举所有数对，时间复杂度为 O(n²)，对于 n = 10⁵ 的数据规模会超时。

优化思路：

  1. 按位处理：由于数位差是逐位比较的，我们可以分别计算每个位置上的贡献
  2. 计数优化：对于每个位置，统计每个数字（0-9）出现的次数
  3. 数学计算：如果数字 d 在某位置出现 c 次，那么它与其他不同数字的配对次数为 c × (n-c)

具体步骤：

  1. 将每个数按位分解，存储每个位置上的数字
  2. 对每个位置，统计 0-9 每个数字的出现次数
  3. 对每个数字，计算它与其他数字的不同次数：count[i] × (n - count[i])
  4. 将所有位置的结果相加

这种方法的时间复杂度为 O(n × d)，其中 d 是数字位数，空间复杂度为 O(d × 10)。

代码实现

class Solution {
public:
    long long sumDigitDifferences(vector<int>& nums) {
        int n = nums.size();
        if (n <= 1) return 0;
        
        // 获取数字位数
        int digits = to_string(nums[0]).length();
        
        long long result = 0;
        
        // 对每一位进行处理
        for (int pos = 0; pos < digits; pos++) {
            vector<int> count(10, 0);
            
            // 统计当前位置上每个数字的出现次数
            for (int num : nums) {
                int digit = (num / (int)pow(10, digits - 1 - pos)) % 10;
                count[digit]++;
            }
            
            // 计算当前位置的贡献
            for (int i = 0; i < 10; i++) {
                if (count[i] > 0) {
                    result += (long long)count[i] * (n - count[i]);
                }
            }
        }
        
        return result / 2; // 因为每一对被计算了两次
    }
};

class Solution:
    def sumDigitDifferences(self, nums: List[int]) -> int:
        n = len(nums)
        if n <= 1:
            return 0
        
        # 获取数字位数
        digits = len(str(nums[0]))
        
        result = 0
        
        # 对每一位进行处理
        for pos in range(digits):
            count = [0] * 10
            
            # 统计当前位置上每个数字的出现次数
            for num in nums:
                digit = (num // (10 ** (digits - 1 - pos))) % 10
                count[digit] += 1
            
            # 计算当前位置的贡献
            for c in count:
                if c > 0:
                    result += c * (n - c)
        
        return result // 2  # 因为每一对被计算了两次

public class Solution {
    public long SumDigitDifferences(int[] nums) {
        int n = nums.Length;
        if (n <= 1) return 0;
        
        // 获取数字位数
        int digits = nums[0].ToString().Length;
        
        long result = 0;
        
        // 对每一位进行处理
        for (int pos = 0; pos < digits; pos++) {
            int[] count = new int[10];
            
            // 统计当前位置上每个数字的出现次数
            foreach (int num in nums) {
                int digit = (num / (int)Math.Pow(10, digits - 1 - pos)) % 10;
                count[digit]++;
            }
            
            // 计算当前位置的贡献
            for (int i = 0; i < 10; i++) {
                if (count[i] > 0) {
                    result += (long)count[i] * (n - count[i]);
                }
            }
        }
        
        return result / 2; // 因为每一对被计算了两次
    }
}

var sumDigitDifferences = function(nums) {
    const n = nums.length;
    if (n <= 1) return 0;
    
    // 获取数字位数
    const digits = nums[0].toString().length;
    
    let result = 0;
    
    // 对每一位进行处理
    for (let pos = 0; pos < digits; pos++) {
        const count = new Array(10).fill(0);
        
        // 统计当前位置上每个数字的出现次数
        for (const num of nums) {
            const digit = Math.floor(num / Math.pow(10, digits - 1 - pos)) % 10;
            count[digit]++;
        }
        
        // 计算当前位置的贡献
        for (let i = 0; i < 10; i++) {
            if (count[i] > 0) {
                result += count[i] * (n - count[i]);
            }
        }
    }
    
    return Math.floor(result / 2); // 因为每一对被计算了两次
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n × d)n 为数组长度，d 为数字位数，需要遍历每个数字的每一位
空间复杂度O(1)只使用了固定大小的计数数组（长度为10），不随输入规模变化

相关题目