By Long Luo
今天 LeetCode 第320场周赛 中第一题是 2475. 数组中不等三元组的数目 ，本文是该题的题解，同时发表在 这里 。
参考了 @灵茶山艾府 的题解 非暴力做法 ，实际上我们可以不用先排序，而是先用 \(\texttt{HashMap}\) 统计数组 \(\textit{num}\) 元素频率。
之后遍历 \(\texttt{HashMap}\) ，结果为：
\[ \sum_{j = 0}^{n} (map[0] + \cdots + map[i]) \times map[j] \times (map[k] + \cdots + map[n - 1]) \]
，其中 \(n\) 为 \(\textit{nums}\) 的长度。
证明如下：
对于数组中的元素 \(x\) ，可以得到：
- 小于 \(x\) 的数有 \(a\) 个；
- 等于 \(x\) 的数有 \(b\) 个；
- 大于 \(x\) 的数有 \(c\) 个。
那么 \(x\) 对最终答案的贡献是 \(abc\) 。
即使 \(x\) 是三元组中的最大或最小值，由于 \(i, j, k\) 的对称性，很明显其实和 \(x\) 是中间值都是同一个答案。
证毕！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public int unequalTriplets(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
for (int x : nums) {
map.put(x, map.getOrDefault(x, 0) + 1);
}
int ans = 0;
int left = 0;
int right = nums.length;
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
int cnt = entry.getValue();
right -= cnt;
ans += left * cnt * right;
left += cnt;
}
return ans;
}
}
|
复杂度分析
- 时间复杂度：\(O(n)\) ，其中 \(n\) 为 \(\textit{nums}\) 的长度。
- 空间复杂度：\(O(n)\) 。
数学：组合
在方法一的基础上，实际上我们还有一种更快的方法，就是利用中学数学里学过的 排列组合 .
详细题解：The Fastest O(n) Solution: Math Combinations 。
代码如下所示：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public int unequalTriplets(int[] nums) {
int n = nums.length;
Map<Integer, Integer> map = new HashMap<>();
for (int x : nums) {
map.put(x, map.getOrDefault(x, 0) + 1);
}
int ans = n * (n - 1) * (n - 2) / 6;
for (int cnt : map.values()) {
if (cnt < 2) {
continue;
}
int same3cnt = cnt * (cnt - 1) * (cnt - 2) / 6;
int same2cnt = (n - cnt) * cnt * (cnt - 1) / 2;
ans -= same3cnt + same2cnt;
}
return ans;
}
}
|
复杂度分析
- 时间复杂度：\(O(n)\) ，其中 \(n\) 为 \(\textit{nums}\) 的长度。
- 空间复杂度：\(O(n)\) 。
All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions . 😉😃💗
