3153. 所有数对中数位差之和

题目描述

你有一个数组 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⁵
1 <= nums[i] < 10⁹
nums 中的整数都有相同的数位长度。

解法

方法一：计数

我们先获取数组中数字的位数 \(m\)，然后对于每一位，我们统计数组 \(\textit{nums}\) 中每个数字在该位上的出现次数，记为 \(\textit{cnt}\)。那么在该位上，所有数对的数位不同之和为：

\[ \sum_{v \in \textit{cnt}} v \times (n - v) \]

其中 \(n\) 是数组的长度。我们将所有位的数位不同之和相加，再除以 \(2\) 即可得到答案。

时间复杂度 \(O(n \times m)\)，空间复杂度 \(O(C)\)，其中 \(n\) 和 \(m\) 分别是数组的长度和数字的位数；而 \(C\) 是常数，本题中 \(C = 10\)。

Python3JavaC++GoTypeScript

class Solution:
    def sumDigitDifferences(self, nums: List[int]) -> int:
        n = len(nums)
        m = int(log10(nums[0])) + 1
        ans = 0
        for _ in range(m):
            cnt = Counter()
            for i, x in enumerate(nums):
                nums[i], y = divmod(x, 10)
                cnt[y] += 1
            ans += sum(v * (n - v) for v in cnt.values()) // 2
        return ans

class Solution {
    public long sumDigitDifferences(int[] nums) {
        int n = nums.length;
        int m = (int) Math.floor(Math.log10(nums[0])) + 1;
        int[] cnt = new int[10];
        long ans = 0;
        for (int k = 0; k < m; ++k) {
            Arrays.fill(cnt, 0);
            for (int i = 0; i < n; ++i) {
                ++cnt[nums[i] % 10];
                nums[i] /= 10;
            }
            for (int i = 0; i < 10; ++i) {
                ans += 1L * cnt[i] * (n - cnt[i]);
            }
        }
        return ans / 2;
    }
}

class Solution {
public:
    long long sumDigitDifferences(vector<int>& nums) {
        int n = nums.size();
        int m = floor(log10(nums[0])) + 1;
        int cnt[10];
        long long ans = 0;
        for (int k = 0; k < m; ++k) {
            memset(cnt, 0, sizeof(cnt));
            for (int i = 0; i < n; ++i) {
                ++cnt[nums[i] % 10];
                nums[i] /= 10;
            }
            for (int i = 0; i < 10; ++i) {
                ans += 1LL * cnt[i] * (n - cnt[i]);
            }
        }
        return ans / 2;
    }
};

func sumDigitDifferences(nums []int) (ans int64) {
    n := len(nums)
    m := int(math.Floor(math.Log10(float64(nums[0])))) + 1
    for k := 0; k < m; k++ {
        cnt := [10]int{}
        for i, x := range nums {
            cnt[x%10]++
            nums[i] /= 10
        }
        for _, v := range cnt {
            ans += int64(v) * int64(n-v)
        }
    }
    ans /= 2
    return
}

function sumDigitDifferences(nums: number[]): number {
    const n = nums.length;
    const m = Math.floor(Math.log10(nums[0])) + 1;
    let ans: bigint = BigInt(0);
    for (let k = 0; k < m; ++k) {
        const cnt: number[] = Array(10).fill(0);
        for (let i = 0; i < n; ++i) {
            ++cnt[nums[i] % 10];
            nums[i] = Math.floor(nums[i] / 10);
        }
        for (let i = 0; i < 10; ++i) {
            ans += BigInt(cnt[i]) * BigInt(n - cnt[i]);
        }
    }
    ans /= BigInt(2);
    return Number(ans);
}

3153. 所有数对中数位差之和

题目描述

解法

方法一：计数

评论