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

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

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