526互联

[LeetCode] 2475. Number of Unequal Triplets in Array

发布时间 2023-06-13 13:29:01作者: CNoodle

You are given a 0-indexed array of positive integers nums. Find the number of triplets (i, j, k) that meet the following conditions:

  • 0 <= i < j < k < nums.length
  • nums[i], nums[j], and nums[k] are pairwise distinct.
    • In other words, nums[i] != nums[j], nums[i] != nums[k], and nums[j] != nums[k].

Return the number of triplets that meet the conditions.

Example 1:

Input: nums = [4,4,2,4,3]
Output: 3
Explanation: The following triplets meet the conditions:
- (0, 2, 4) because 4 != 2 != 3
- (1, 2, 4) because 4 != 2 != 3
- (2, 3, 4) because 2 != 4 != 3
Since there are 3 triplets, we return 3.
Note that (2, 0, 4) is not a valid triplet because 2 > 0.

Example 2:

Input: nums = [1,1,1,1,1]
Output: 0
Explanation: No triplets meet the conditions so we return 0.

Constraints:

  • 3 <= nums.length <= 100
  • 1 <= nums[i] <= 1000

数组中不等三元组的数目。

给你一个下标从 0 开始的正整数数组 nums 。请你找出并统计满足下述条件的三元组 (i, j, k) 的数目：

0 <= i < j < k < nums.length
nums[i]、nums[j] 和 nums[k] 两两不同 。
换句话说：nums[i] != nums[j]、nums[i] != nums[k] 且 nums[j] != nums[k] 。
返回满足上述条件三元组的数目。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/number-of-unequal-triplets-in-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题有多种思路，这里我提供一个次优解。

注意题目的数据范围，这道题可以用暴力解做，时间复杂度是O(n^3)。

我的思路是 hashmap + 排序。分如下几步

  • 用 hashmap 统计 input 数组中每个不同元素分别出现了几次
  • 对 input 数组排序
  • 再次扫描 input 数组，以当前扫描到的元素 nums[i] 为中间元素所组成的三元组的数量 = nums[i] 左边元素的个数 * nums[i] 的个数 * 剩下元素的个数

时间O(n^2)

空间O(n)

Java实现

 1 class Solution {
 2     public int unequalTriplets(int[] nums) {
 3         HashMap<Integer, Integer> map = new HashMap<>();
 4         for (int num : nums) {
 5             map.put(num, map.getOrDefault(num, 0) + 1);
 6         }
 7         
 8         int res = 0;
 9         Arrays.sort(nums);
10         int n = nums.length;
11         // i 指向中间的元素的第一个位置
12         // [0, ......, i, ....., i + j, .....,n - 1]
13         int i = 0;
14         while (i < nums.length) {
15             int j = map.get(nums[i]);
16             // 0 - i这一段是左边元素
17             // i - i + j这一段是中间元素
18             // i + j到最后是右边元素
19             res += i * j * (n - i - j);
20             i += j;
21         }
22         return res;
23     }
24 }

 

LeetCode 题目总结