题目描述

车尔尼有一个数组 nums，它只包含 正 整数，所有正整数的数位长度都 相同 。

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

请车尔尼返回 nums 中 所有 整数对里，数位不同之和。

样例

输入：nums = [13,23,12]

输出：4

解释：
计算过程如下：
- 13 和 23 的数位不同为 1。
- 13 和 12 的数位不同为 1。
- 23 和 12 的数位不同为 2。
所以所有整数数对的数位不同之和为 1 + 1 + 2 = 4。

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

输出：0

解释：
数组中所有整数都相同，所以所有整数数对的数位不同之和为 0。

限制

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

算法

(计算贡献) $O((n + \Sigma) \log U)$

1. 独立计算每一位产生的贡献。
2. 对于第 $i$ 位，计算出这一位中每种数字的出现次数 $seen$。然后对于第 $j$ 种数字，其贡献的答案为 $seen(j) \cdot (n - seen(j))$。
3. 注意到，按照上述计算方式，每一对不同的数位都计算了两次，所以需要最后将答案除以 2。

时间复杂度

• 每个数位遍历所有数字一次，故时间复杂度为 $O(n)$。

空间复杂度

• 仅需要 $O(|\Sigma|)$ 的额外空间存储每一种数字的出现次数。

C++ 代码

#define LL long long

class Solution {
public:
    LL sumDigitDifferences(vector<int>& nums) {
        const int n = nums.size();
        LL ans = 0;

        for (int i = 0; i < 10; i++) {
            vector<int> seen(10, 0);
            for (int &x : nums) {
                ++seen[x % 10];
                x /= 10;
            }

            for (int j = 0; j < 10; j++)
                ans += (LL)(seen[j]) * (n - seen[j]);
        }

        return ans / 2;
    }
};