3153. 所有数对中数位不同之和（24.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 中的整数都有相同的数位长度。

解题思路

见代码

代码

class Solution {
public:long long sumDigitDifferences(vector<int>& nums) {int n=nums.size();//nums 中的整数都有相同的数位长度 int len=to_string(nums[0]).size();//数的位数  long long ans=0;vector<array<int,10>> cnt(len);/*此处相当于 cnt[数的位数][0~9的数字]对于例1而论：个  十1   32   31   2对于第 n 个数字的第 i 位而言，假设此位的数字时 a：cnt[i][a]的数表示为前 n 个数在 i 位出现的数字 a 的个数，即与此数的此位相同的数的个数对于此数的 i 位而言，n - cnt[i][a] 则表示不同的个数对于第 1 位而言，1 2 1，//第一个数为：0-0，即第一个数在第一位没有不同的个数//第二个数为：1-0，即第一个数在第一位有 1 不同的个数   //第三个数为：2-1，即第一个数在第一位有 1 不同的个数  */for(int i=0;i<n;i++){int num=nums[i];int wei=0;while(num){ans+=i-cnt[wei][num%10];cnt[wei++][num%10]++;num/=10;}}return ans;}
};