巧用哈希表与组合数学：高效求解序列中独特三元组数量

要解决这个问题，我们需要找到满足以下条件的三元组 (i, j, k) 的数量： 1. 1 ≤ i < j < k ≤ n 2. ai, aj, ak 三个元素互不相同 我们可以使用三重循环来暴力求解这个问题，但这种方法的时间复杂度是 O(n^3)，在 n 较大时会超时。我们需要优化算法。 一个更高效的方法是利用哈希表来记录每个元素出现的次数，然后通过组合数学的方法来计算符合条件的三元组数量。具体步骤如下： 1. 遍历序列，统计每个元素的出现次数。 2. 对于每个元素 ai，计算有多少不同的元素 aj 和 ak 可以与它组成三元组。 3. 使用组合公式 C(m, 2) = m * (m - 1) / 2 来计算不同元素的组合数。 下面是 Python 实现代码： ```python def count_unique_triplets(n, sequence): from collections import defaultdict # Step 1: Count the frequency of each element in the sequence frequency = defaultdict(int) for num in sequence: frequency[num] += 1 # Step 2: Calculate the number of unique triplets total_triplets = 0 for num in frequency: count = frequency[num] if count >= 3: # If there are at least three occurrences of the same number, we can form multiple triplets total_triplets += count * (count - 1) * (count - 2) // 6 elif count == 2: # If there are exactly two occurrences, we need to pair it with other distinct numbers for other_num in frequency: if other_num != num and frequency[other_num] > 0: total_triplets += count * (count - 1) // 2 * frequency[other_num] elif count == 1: # If there is only one occurrence, we need to pair it with two other distinct numbers for other_num1 in frequency: if other_num1 != num: for other_num2 in frequency: if other_num2 != num and other_num2 != other_num1: total_triplets += count * frequency[other_num1] * frequency[other_num2] return total_triplets # Read input n = int(input()) sequence = list(map(int, input().split())) # Get the result result = count_unique_triplets(n, sequence) print(result) ``` 解释 1. 频率统计：我们使用 `defaultdict` 来统计每个元素在序列中出现的次数。 2. 计算三元组：根据每个元素的频率，我们分别处理三种情况： - 如果某个元素出现至少三次，可以直接用组合公式计算。 - 如果某个元素出现两次，需要与其他不同的元素配对。 - 如果某个元素只出现一次，需要与其他两个不同的元素配对。 3. 输出结果：最后输出符合条件的三元组数量。 这种方法的时间复杂度为 O(n^2)，在大多数情况下都能在 1000ms 内完成。 ######[AI写代码神器 | 754点数解答 | 2024-11-08 20:18:41]