数组中不等三元组的数目【LC2475】
给你一个下标从 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]
。返回满足上述条件三元组的数目*。*
暴力
-
思路:使用三个指针暴力搜寻合法的位置
-
实现
class Solution {public int unequalTriplets(int[] nums) {int len = nums.length;int res = 0;if (len < 3){return res;}int i = 0;while (i < len - 2){int j = i + 1;while (j < len - 1){if (nums[i] != nums[j]){int k = j + 1;while (k < len){if (nums[j] != nums[k] && nums[i] != nums[k]){res++; }k++;}}j++;}i++;}return res;} }
-
复杂度
- 时间复杂度: O ( n 3 ) O(n^3) O(n3)
- 空间复杂度: O ( 1 ) O(1) O(1)
-
排序
-
思路:对于数组中某一个元素 x x x,假设
- 大于其的元素有a个
- 等于其的元素有b个
- 小于其的元素有c个
那么,根据组合原理,该元素对结果的贡献为 a ∗ b ∗ c a*b*c a∗b∗c
-
实现
class Solution {public int unequalTriplets(int[] nums) {Arrays.sort(nums);int l = 0;int ans = 0;int len = nums.length;while (l < len ){int r = l + 1;// 寻找与nums[l]不相等的第一个数while (r < len && nums[l] == nums[r]){r++;}ans += l * (r - l) * ( len - r);l = r; }return ans;} }
-
复杂度
- 时间复杂度: O ( n l o g n ) O(nlogn) O(nlogn)
- 空间复杂度: O ( l o g n ) O(logn) O(logn)
哈希表
-
思路:由于三元组中元素的数值的顺序是不重要的,只需要值不相等既可,因此可以直接用哈希表统计num出现的次数,然后遍历哈希表,假设
- 在其之前遍历的元素有a个
- 等于其的元素有b个
- 在其之后遍历的元素有c个
那么,根据组合原理,该元素对结果的贡献为 a ∗ b ∗ c a*b*c a∗b∗c
-
实现
class Solution {public int unequalTriplets(int[] nums) {Map<Integer,Integer> map = new HashMap<>();int ans = 0;int len = nums.length;for (int i = 0; i < len; i++){map.put(nums[i], map.getOrDefault(nums[i],0) + 1);}int l = 0;int r = len;for (Map.Entry<Integer,Integer> node : map.entrySet()){int count = node.getValue();r -= count;ans += l * count * r;l += count;}return ans;} }
-
复杂度
- 时间复杂度: O ( n ) O(n) O(n)
- 空间复杂度: O ( n ) O(n) O(n)