跳转至

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 <= 105
  • 1 <= nums[i] < 109
  • 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$。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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);
}

评论