标签: 数学
难度: Medium
标签: 数学
难度: Medium
运行时间: 208 ms
内存: 22.5 MB
g=defaultdict(list) for i in range(1,101): for j in range(1,101): for k in range(j,101): if (i+j+k)%i==0 and (i+j+k)%j!=0 and (i+j+k)%k!=0: g[i].append((j,k)) class Solution: def singleDivisorTriplet(self, nums: List[int]) -> int: res=0 cnt=Counter(nums) for a in set(nums): for b,c in g[a]: if b!=c: res+=cnt[a]*cnt[b]*cnt[c]*6 else: res+=cnt[a]*comb(cnt[b],2)*6 return res
本题解首先使用一个嵌套的循环构建一个字典 g,字典的键为 i,值为满足特定条件的二元组 (j, k) 的列表。特定条件是:i+j+k 除以 i 的余数为 0,除以 j 和 k 的余数不为 0。这表示 i 是 i+j+k 的唯一因子。在 Solution 类的 singleDivisorTriplet 方法中,首先初始化结果 res 为 0,并使用计数器 cnt 来记录 nums 中每个数字的出现次数。遍历 nums 中的唯一数字 a,对于每个 a,从字典 g 中找到所有符合条件的 (b, c)。如果 b 和 c 不相等,计算可能的三元组数量,并乘以 6(因为三元组 (a, b, c) 可以有 6 种不同的排列)。如果 b 和 c 相等,则需要特殊处理,使用组合数计算 b 选 2 的方式,并同样乘以 6。最终,返回计算出的结果 res。
时间复杂度: O(n^2)
空间复杂度: O(n^2)
g=defaultdict(list) # 创建一个默认为列表的字典 for i in range(1,101): # i 从 1 到 100 for j in range(1,101): # j 从 1 到 100 for k in range(j,101): # k 从 j 到 100,确保 k >= j if (i+j+k)%i==0 and (i+j+k)%j!=0 and (i+j+k)%k!=0: # 检查条件 g[i].append((j,k)) # 添加满足条件的二元组到字典 class Solution: def singleDivisorTriplet(self, nums: List[int]) -> int: res=0 # 结果初始化为 0 cnt=Counter(nums) # 计数 nums 中每个元素的出现次数 for a in set(nums): # 遍历 nums 中的每个唯一元素 for b,c in g[a]: # 遍历字典中与 a 关联的所有 (b, c) 对 if b!=c: # 如果 b 和 c 不相同 res+=cnt[a]*cnt[b]*cnt[c]*6 # 计算排列组合的数量 else: # 如果 b 和 c 相同 res+=cnt[a]*comb(cnt[b],2)*6 # 使用组合计算数量 return res # 返回结果
这个设计是为了确保在三元组中,i是唯一的因子。如果i+j+k除以i的余数为0,说明i是i+j+k的因子。如果i+j+k除以j和k的余数都不为0,则j和k不是i+j+k的因子。这样设计确保了i是三个数之和i+j+k的唯一因子,满足题目的单因数三元组的要求。
将k的循环起始于j(k从j开始)的设计是为了避免在字典g中重复记录元组,同时确保b和c的关系(b <= c)不会影响组合的对称性。这样做可以避免不必要的计算和存储重复的数据,例如避免记录(b, c)和(c, b)两次,优化了空间和计算效率。
当b和c相等时,元素b在数组中的实际可用数量会影响可能的组合。使用组合数计算方式是因为需要从数量为cnt[b]的b中选择两个来组成三元组,这里的组合数计算方式为comb(cnt[b], 2),表示从cnt[b]个b中选择两个的不同方式。这种计算方式确保了在b和c相等时计数的正确性和公平性。
使用defaultdict(list)来构建字典g的好处在于,当访问一个尚未在字典中存在的键时,defaultdict会自动为该键创建一个新的空列表。这样可以避免在添加元素之前需要检查键是否存在于字典中,从而简化代码并提高效率。defaultdict(list)在处理这种类型的数据累积场景中特别有用,使代码更加简洁和高效。