LeetCode 3153.所有数对中数位差之和：计数

【LetMeFly】3153.所有数对中数位差之和：计数

力扣题目链接：https://leetcode.cn/problems/sum-of-digit-differences-of-all-pairs/

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

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

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

示例 1：

输出：4

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

示例 2：

输出：0

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

提示：

• 2 <= nums.length <= 105
• 1 <= nums[i] < 109
• nums 中的整数都有相同的数位长度。

解题方法：计数

首先需要明确每一位互不干扰，因此每一位分开计算，然后加起来就好了。

对于每个数的每一位，假设有3个0、2个1和4个2，那么“不同数字的数目”是什么呢？

不同数字的数目为$3\times (2+4)+2\times (3+4)+4\times (3+2)=3\times (9-3)+2\times (9-2)+4\times (9-4)$。

也就是说，统计一下每个数字出现的次数就好了。

• 时间复杂度$O(n\log M)$，其中$M$是每个数的最大范围
• 空间复杂度$O(C)$，其中$C=10$

AC代码

C++

typedef long long ll;
class Solution {
public:
    ll sumDigitDifferences(vector<int>& nums) {
        ll ans = 0;
        do {
            ll times[10] = {0};
            for (int& t : nums) {
                times[t % 10]++;
                t /= 10;
            }
            for (int i = 0; i < 10; i++) {
                ans += times[i] * (nums.size() - times[i]);
            }
        } while (nums[0]);
        return ans / 2;
    }
};

Go

package main

func sumDigitDifferences(nums []int) int64 {
    ans := int64(0)
    for nums[0] > 0 {
        times := make([]int, 10)
        for i, n := range nums {
            times[n % 10]++
            nums[i] /= 10
        }
        for i := 0; i < 10; i++ {
            ans += int64(times[i] * (len(nums) - times[i]))
        }
    }
    return ans / 2
}

Java

class Solution {
    public long sumDigitDifferences(int[] nums) {
        long ans = 0;
        while (nums[0] > 0) {
            long[] times = new long[10];
            for (int i = 0; i < nums.length; i++) {
                times[nums[i] % 10]++;
                nums[i] /= 10;
            }
            for (int i = 0; i < 10; i++) {
                ans += times[i] * (nums.length - times[i]);
            }
        }
        return ans / 2;
    }
}

Python

from typing import List

class Solution:
    def sumDigitDifferences(self, nums: List[int]) -> int:
        ans = 0
        n = max(nums)
        while n:  # while nums[0]的话可能会有[0, 1]的情况  # 后续更新：忽然发现题目限定是正数，有点过考虑了
            n //= 10
            times = [0] * 10
            for th, x in enumerate(nums):
                times[x % 10] += 1
                nums[th] //= 10
            for i in range(10):
                ans += times[i] * (len(nums) - times[i])
        return ans // 2

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/141729979