class Solution {
public:
long long sumDigitDifferences(vector<int>& nums) {
}
};
100300. 所有数对中数位不同之和
车尔尼有一个数组 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 <= 1051 <= nums[i] < 109nums 中的整数都有相同的数位长度。原站题解
rust 解法, 执行用时: 14 ms, 内存消耗: 3.3 MB, 提交时间: 2024-08-30 10:16:31
impl Solution {
pub fn sum_digit_differences(nums: Vec<i32>) -> i64 {
let mut nums = nums.clone();
let mut res: i64 = 0;
let n = nums.len();
while (nums[0] > 0) {
let mut cnt = vec![0; 10];
for i in 0..n {
cnt[nums[i] as usize % 10] += 1;
nums[i] /= 10;
}
for i in 0..10 {
res += (n - cnt[i]) as i64 * (cnt[i]) as i64;
}
}
return res / 2;
}
}
javascript 解法, 执行用时: 98 ms, 内存消耗: 61.5 MB, 提交时间: 2024-08-30 10:16:11
/**
* @param {number[]} nums
* @return {number}
*/
var sumDigitDifferences = function(nums) {
let res = 0n;
let n = nums.length;
while (nums[0] > 0) {
const cnt = new 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++) {
res += BigInt(n - cnt[i]) * BigInt(cnt[i]);
}
}
return Number(res >> 1n);
};
golang 解法, 执行用时: 89 ms, 内存消耗: 8.4 MB, 提交时间: 2024-05-19 23:38:14
func sumDigitDifferences(nums []int) int64 {
n, m := len(nums), len(strconv.Itoa(nums[0]))
ans := m * n * (n - 1) / 2
cnt := make([][10]int, m)
for _, x := range nums {
for i := 0; x > 0; x /= 10 {
d := x % 10
ans -= cnt[i][d]
cnt[i][d]++
i++
}
}
return int64(ans)
}
// 2
func sumDigitDifferences2(nums []int) (ans int64) {
cnt := make([][10]int, len(strconv.Itoa(nums[0])))
for k, x := range nums {
for i := 0; x > 0; x /= 10 {
d := x % 10
ans += int64(k - cnt[i][d])
cnt[i][d]++
i++
}
}
return
}
cpp 解法, 执行用时: 125 ms, 内存消耗: 100.8 MB, 提交时间: 2024-05-19 23:37:48
class Solution {
public:
long long sumDigitDifferences(vector<int>& nums) {
long long ans = 0;
vector<array<int, 10>> cnt(to_string(nums[0]).length());
for (int k = 0; k < nums.size(); k++) {
int x = nums[k];
for (int i = 0; x; x /= 10, i++) {
int d = x % 10;
ans += k - cnt[i][d]++;
}
}
return ans;
}
// 2
long long sumDigitDifferences2(vector<int>& nums) {
long long n = nums.size(), m = to_string(nums[0]).length();
long long ans = m * n * (n - 1) / 2;
vector<array<int, 10>> cnt(m);
for (int x : nums) {
for (int i = 0; x; x /= 10) {
ans -= cnt[i++][x % 10]++;
}
}
return ans;
}
};
java 解法, 执行用时: 15 ms, 内存消耗: 57.7 MB, 提交时间: 2024-05-19 23:37:22
public class Solution {
public long sumDigitDifferences(int[] nums) {
int n = nums.length;
int m = Integer.toString(nums[0]).length();
long ans = (long) m * n * (n - 1) / 2;
int[][] cnt = new int[m][10];
for (int x : nums) {
for (int i = 0; x > 0; x /= 10) {
ans -= cnt[i++][x % 10]++;
}
}
return ans;
}
// 2
public long sumDigitDifferences2(int[] nums) {
long ans = 0;
int[][] cnt = new int[Integer.toString(nums[0]).length()][10];
for (int k = 0; k < nums.length; k++) {
int x = nums[k];
for (int i = 0; x > 0; x /= 10, i++) {
int d = x % 10;
ans += k - cnt[i][d]++;
}
}
return ans;
}
}
python3 解法, 执行用时: 453 ms, 内存消耗: 30.2 MB, 提交时间: 2024-05-19 23:36:46
class Solution:
def sumDigitDifferences(self, nums: List[int]) -> int:
ans = 0
cnt = [[0] * 10 for _ in str(nums[0])]
for k, x in enumerate(nums):
i = 0
while x:
x, d = divmod(x, 10)
ans += k - cnt[i][d]
cnt[i][d] += 1
i += 1
return ans
# 逆向思维
def sumDigitDifferences2(self, nums: List[int]) -> int:
n, m = len(nums), len(str(nums[0]))
ans = m * n * (n - 1) // 2
cnt = [[0] * 10 for _ in range(m)]
for x in nums:
i = 0
while x:
x, d = divmod(x, 10)
ans -= cnt[i][d]
cnt[i][d] += 1
i += 1
return ans