[LeetCode][2475. 数组中不等三元组的数目] 2种 O(n) 时间复杂度算法

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 1.7k 阅读时长 ≈ 2 分钟

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);
        }

        // total combinations
        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. 😉😃💗