class Solution {
public:
int subsequencesWithMiddleMode(vector<int>& nums) {
}
};
3395. 唯一中间众数子序列 I
给你一个整数数组 nums ，请你求出 nums 中大小为 5 的子序列的数目，它是 唯一中间众数序列 。
由于答案可能很大，请你将答案对 109 + 7 取余 后返回。
众数 指的是一个数字序列中出现次数 最多 的元素。
如果一个数字序列众数只有一个，我们称这个序列有 唯一众数 。
一个大小为 5 的数字序列 seq ，如果它中间的数字（seq[2]）是唯一众数，那么称它是 唯一中间众数 序列。
子序列 指的是将一个数组删除一些（也可以不删除）元素后，剩下元素不改变顺序得到的 非空 数组。
示例 1：
输入：nums = [1,1,1,1,1,1]
输出：6
解释：
[1, 1, 1, 1, 1] 是唯一长度为 5 的子序列。1 是它的唯一中间众数。有 6 个这样的子序列，所以返回 6 。
示例 2：
输入：nums = [1,2,2,3,3,4]
输出：4
解释：
[1, 2, 2, 3, 4] 和 [1, 2, 3, 3, 4] 都有唯一中间众数，因为子序列中下标为 2 的元素在子序列中出现次数最多。[1, 2, 2, 3, 3] 没有唯一中间众数，因为 2 和 3 都出现了两次。
示例 3：
输入：nums = [0,1,2,3,4,5,6,7,8]
输出：0
解释：
没有长度为 5 的唯一中间众数子序列。
提示：
5 <= nums.length <= 1000-109 <= nums[i] <= 109原站题解
golang 解法, 执行用时: 144 ms, 内存消耗: 8.5 MB, 提交时间: 2024-12-26 09:32:19
func comb2(num int) int {
return num * (num - 1) / 2
}
func subsequencesWithMiddleMode(nums []int) int {
n := len(nums)
ans := n * (n - 1) * (n - 2) * (n - 3) * (n - 4) / 120 // 所有方案数
suf := map[int]int{}
for _, x := range nums {
suf[x]++
}
pre := make(map[int]int, len(suf)) // 预分配空间
// 枚举 x，作为子序列正中间的数
for left, x := range nums[:n-2] {
suf[x]--
if left > 1 {
right := n - 1 - left
preX, sufX := pre[x], suf[x]
// 不合法：只有一个 x
ans -= comb2(left-preX) * comb2(right-sufX)
// 不合法：只有两个 x，且至少有两个 y（y != x）
for y, sufY := range suf { // 注意 sufY 可能是 0
if y == x {
continue
}
preY := pre[y]
// 左边有两个 y，右边有一个 x，即 yy x xz（z 可以等于 y）
ans -= comb2(preY) * sufX * (right - sufX)
// 右边有两个 y，左边有一个 x，即 zx x yy（z 可以等于 y）
ans -= comb2(sufY) * preX * (left - preX)
// 左右各有一个 y，另一个 x 在左边，即 xy x yz（z != y）
ans -= preY * sufY * preX * (right - sufX - sufY)
// 左右各有一个 y，另一个 x 在右边，即 zy x xy（z != y）
ans -= preY * sufY * sufX * (left - preX - preY)
}
}
pre[x]++
}
return ans % 1_000_000_007
}
java 解法, 执行用时: 206 ms, 内存消耗: 44.3 MB, 提交时间: 2024-12-26 09:32:07
class Solution {
public int subsequencesWithMiddleMode(int[] nums) {
int n = nums.length;
long ans = (long) n * (n - 1) * (n - 2) * (n - 3) * (n - 4) / 120; // 所有方案数
Map<Integer, Integer> suf = new HashMap<>();
for (int x : nums) {
suf.merge(x, 1, Integer::sum); // suf[x]++
}
Map<Integer, Integer> pre = new HashMap<>(suf.size()); // 预分配空间
// 枚举 x，作为子序列正中间的数
for (int left = 0; left < n - 2; left++) {
int x = nums[left];
suf.merge(x, -1, Integer::sum); // suf[x]--
if (left > 1) {
int right = n - 1 - left;
int preX = pre.getOrDefault(x, 0);
int sufX = suf.get(x);
// 不合法：只有一个 x
ans -= (long) comb2(left - preX) * comb2(right - sufX);
// 不合法：只有两个 x，且至少有两个 y（y != x）
for (Map.Entry<Integer, Integer> e : suf.entrySet()) {
int y = e.getKey();
if (y == x) {
continue;
}
int sufY = e.getValue(); // 注意 sufY 可能是 0
int preY = pre.getOrDefault(y, 0);
// 左边有两个 y，右边有一个 x，即 yy x xz（z 可以等于 y）
ans -= (long) comb2(preY) * sufX * (right - sufX);
// 右边有两个 y，左边有一个 x，即 zx x yy（z 可以等于 y）
ans -= (long) comb2(sufY) * preX * (left - preX);
// 左右各有一个 y，另一个 x 在左边，即 xy x yz（z != y）
ans -= (long) preY * sufY * preX * (right - sufX - sufY);
// 左右各有一个 y，另一个 x 在右边，即 zy x xy（z != y）
ans -= (long) preY * sufY * sufX * (left - preX - preY);
}
}
pre.merge(x, 1, Integer::sum); // pre[x]++
}
return (int) (ans % 1_000_000_007);
}
private int comb2(int num) {
return num * (num - 1) / 2;
}
}
cpp 解法, 执行用时: 122 ms, 内存消耗: 40.5 MB, 提交时间: 2024-12-26 09:31:52
class Solution {
int comb2(int num) {
return num * (num - 1) / 2;
}
public:
int subsequencesWithMiddleMode(vector<int>& nums) {
int n = nums.size();
long long ans = 1LL * n * (n - 1) * (n - 2) * (n - 3) * (n - 4) / 120; // 所有方案数
unordered_map<int, int> pre, suf;
for (int x : nums) {
suf[x]++;
}
// 枚举 x，作为子序列正中间的数
for (int left = 0; left < n - 2; left++) {
int x = nums[left];
suf[x]--;
if (left > 1) {
int right = n - 1 - left;
int pre_x = pre[x], suf_x = suf[x];
// 不合法：只有一个 x
ans -= 1LL * comb2(left - pre_x) * comb2(right - suf_x);
// 不合法：只有两个 x，且至少有两个 y（y != x）
for (auto& [y, suf_y] : suf) { // 注意 suf_y 可能是 0
if (y == x) {
continue;
}
int pre_y = pre[y];
// 左边有两个 y，右边有一个 x，即 yy x xz（z 可以等于 y）
ans -= 1LL * comb2(pre_y) * suf_x * (right - suf_x);
// 右边有两个 y，左边有一个 x，即 zx x yy（z 可以等于 y）
ans -= 1LL * comb2(suf_y) * pre_x * (left - pre_x);
// 左右各有一个 y，另一个 x 在左边，即 xy x yz（z != y）
ans -= 1LL * pre_y * suf_y * pre_x * (right - suf_x - suf_y);
// 左右各有一个 y，另一个 x 在右边，即 zy x xy（z != y）
ans -= 1LL * pre_y * suf_y * suf_x * (left - pre_x - pre_y);
}
}
pre[x]++;
}
return ans % 1'000'000'007;
}
};
python3 解法, 执行用时: 1913 ms, 内存消耗: 18 MB, 提交时间: 2024-12-26 09:31:39
class Solution:
def subsequencesWithMiddleMode(self, nums: List[int]) -> int:
n = len(nums)
suf = Counter(nums)
pre = defaultdict(int)
ans = comb(n, 5) # 所有方案数
# 枚举 x，作为子序列正中间的数
for left, x in enumerate(nums[:-2]):
suf[x] -= 1
if left > 1:
right = n - 1 - left
pre_x, suf_x = pre[x], suf[x]
# 不合法：只有一个 x
ans -= comb(left - pre_x, 2) * comb(right - suf_x, 2)
# 不合法：只有两个 x，且至少有两个 y（y != x）
for y, suf_y in suf.items(): # 注意 suf_y 可能是 0
if y == x:
continue
pre_y = pre[y]
# 左边有两个 y，右边有一个 x，即 yy x xz（z 可以等于 y）
ans -= comb(pre_y, 2) * suf_x * (right - suf_x)
# 右边有两个 y，左边有一个 x，即 zx x yy（z 可以等于 y）
ans -= comb(suf_y, 2) * pre_x * (left - pre_x)
# 左右各有一个 y，另一个 x 在左边，即 xy x yz（z != y）
ans -= pre_y * suf_y * pre_x * (right - suf_x - suf_y)
# 左右各有一个 y，另一个 x 在右边，即 zy x xy（z != y）
ans -= pre_y * suf_y * suf_x * (left - pre_x - pre_y)
pre[x] += 1
return ans % 1_000_000_007