日期: 2024 年 8 月 30 日

目标

你有一个数组 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 中的整数都有相同的数位长度。

思路

有一个数组其元素的数位长度相同，针对数组中所有可能的数对组合（即任选两个元素），比较其数位不同的个数并累加求和。

C(n,2) = n(n-1)/2 时间复杂度为 O(n^2)，再加上数位比较，暴力枚举会超时。

考虑到所有元素的数位 digitLength 相同，那么可以统计所有元素该位上数字出现次数，时间复杂度为 O(digitLength*n)。然后逐数位比较，即在 0~9 之间组合，组合数等于对应数位数字出现次数的乘积。外层数位循环最大为10（可以忽略掉出现次数为0的），内层 0~9 组合数最多(10*9/2)，总循环次数最大450，没有增大数据规模。

代码

/**
 * @date 2024-08-30 9:33
 */
public class SumDigitDifferences3153 {

    public long sumDigitDifferences(int[] nums) {
        int n = nums.length;
        int first = nums[0];
        int digitsLength = 0;
        while (first > 0) {
            digitsLength++;
            first /= 10;
        }
        int[][] cnt = new int[digitsLength][10];
        for (int i = 0; i < n; i++) {
            int d = 0;
            int num = nums[i];
            while (num > 0) {
                cnt[d++][num % 10]++;
                num /= 10;
            }
        }
        long res = 0L;
        for (int[] digit : cnt) {
            for (int i = 0; i < 10; i++) {
                if (digit[i] == 0) {
                    continue;
                }
                for (int j = i + 1; j < 10; j++) {
                    res += (long) digit[i] * digit[j];
                }
            }
        }
        return res;
    }

}

性能