LeetCode 3153. Sum of Digit Differences of All Pairs

周賽 398。大概是近來最簡單的 Q3。

題目

輸入正整數陣列 nums，其中所有整數的位數都相同。

位數差指的是兩個整數之間，相同位置擁有不同數字的個數。

求 nums 中所有數對的位數差的總和。

解法

仔細看看，數對中的數字都是相互獨立的，並不會互相影響。
問題轉換成：求陣列中，由不同元素組成的數對有幾個。如果是 M 位數，就分別計算 M 次。

先將 nums 中的元素成字串，並枚舉字串中第 pos 位的字元。
對於索引 i 的字元 c 來說，可以與左方 i 個字元組成數對。若那 i 個中有 cnt 個字元是 c，則有 i - cnt 個不是 c。

時間複雜度 O(MN)，其中 M = log nums[0]。
空間複雜度 O(N)。

class Solution:
    def sumDigitDifferences(self, nums: List[int]) -> int:
        a = [str(x) for x in nums]
        M = len(a[0])
        ans = 0
        for pos in range(M):
            d = Counter()
            for i, s in enumerate(a):
                c = s[pos]
                ans += i - d[c]
                d[c] += 1
                
        return ans

也可以反向著做，先求出總共有多少數對，再找出同樣字元組成的數對扣掉。

class Solution:
    def sumDigitDifferences(self, nums: List[int]) -> int:
        a = [str(x) for x in nums]
        N = len(nums)
        M = len(a[0])
        tot = N * (N - 1) // 2 * M
        ans = 0
        for pos in range(M):
            d = Counter()
            for s in a:
                c = s[pos]
                ans += d[c]
                d[c] += 1
                
        return tot - ans