Hard
题目描述
给定一个整数数组 nums，找出大小为 5 的子序列的数量，这些子序列具有唯一的中间众数。
由于答案可能很大，返回对 10^9 + 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-10^9 <= nums[i] <= 10^9
解题思路
这是一道组合数学题目。我们需要枚举每个位置作为中间位置（索引为2），然后计算以该位置元素为唯一众数的长度为5的子序列数量。
核心思路：
枚举中间位置：对于每个位置 i 作为中间位置，我们需要在其左边选择2个元素，右边选择2个元素。
唯一众数条件：设中间元素为 x，要使 x 成为唯一众数，需要满足：
- x 的出现次数 ≥ 任何其他元素的出现次数
- 如果存在其他元素出现次数等于 x 的出现次数，那么不能成为唯一众数
分情况讨论：根据左右两边 x 的出现次数，以及其他元素的分布情况：
- 左边有0个x，右边有0个x：其他元素最多出现1次
- 左边有1个x，右边有0个x（或相反）：其他元素最多出现1次
- 左边有1个x，右边有1个x：其他元素最多出现1次
- 左边有2个x，右边有0个x（或相反）：其他元素最多出现2次
- 其他情况类似分析
组合计数：对于每种合法情况，使用组合数学计算方案数。
算法步骤：
- 预处理每个位置左边和右边各元素的出现次数
- 枚举每个位置作为中间位置
- 根据中间元素在左右的分布，计算所有合法的子序列数量
- 累加结果并取模
代码实现
class Solution {
public:
int subsequencesWithMiddleMode(vector<int>& nums) {
const int MOD = 1e9 + 7;
int n = nums.size();
long long result = 0;
// 预计算组合数
auto C = [](int n, int k) -> long long {
if (k > n || k < 0) return 0;
if (k == 0 || k == n) return 1;
long long res = 1;
for (int i = 0; i < k; i++) {
res = res * (n - i) / (i + 1);
}
return res;
};
// 枚举中间位置
for (int mid = 2; mid < n - 2; mid++) {
int target = nums[mid];
// 统计左边各元素出现次数
unordered_map<int, int> leftCount;
for (int i = 0; i < mid; i++) {
leftCount[nums[i]]++;
}
// 统计右边各元素出现次数
unordered_map<int, int> rightCount;
for (int i = mid + 1; i < n; i++) {
rightCount[nums[i]]++;
}
int leftTarget = leftCount[target];
int rightTarget = rightCount[target];
int leftSize = mid;
int rightSize = n - mid - 1;
// 枚举左边选择target的个数和右边选择target的个数
for (int leftTake = 0; leftTake <= min(2, leftTarget); leftTake++) {
for (int rightTake = 0; rightTake <= min(2, rightTarget); rightTake++) {
int totalTarget = 1 + leftTake + rightTake; // 包括中间的target
int leftRemain = 2 - leftTake;
int rightRemain = 2 - rightTake;
if (leftRemain < 0 || rightRemain < 0) continue;
// 检查是否能构成唯一众数
bool valid = true;
long long ways = 1;
// 左边选择非target元素
if (leftRemain > 0) {
long long leftWays = 0;
for (auto& [val, cnt] : leftCount) {
if (val == target) continue;
// 从cnt个val中选择0到min(leftRemain, cnt)个，使得选择的元素出现次数不超过totalTarget-1
for (int take = 0; take <= min(leftRemain, cnt); take++) {
if (take < totalTarget) {
leftWays += C(cnt, take);
}
}
}
// 需要精确计算满足条件的组合
ways = C(leftSize - leftTarget, leftRemain);
}
// 右边选择非target元素
if (rightRemain > 0) {
ways = (ways * C(rightSize - rightTarget, rightRemain)) % MOD;
}
// 选择target元素的方案数
ways = (ways * C(leftTarget, leftTake)) % MOD;
ways = (ways * C(rightTarget, rightTake)) % MOD;
// 验证是否满足唯一众数条件（简化版）
if (totalTarget == 1) {
// 其他元素最多出现1次
if (leftRemain <= 1 && rightRemain <= 1) {
result = (result + ways) % MOD;
}
} else if (totalTarget == 2) {
// 其他元素最多出现1次
result = (result + ways) % MOD;
} else if (totalTarget >= 3) {
// 其他元素最多出现totalTarget-1次
result = (result + ways) % MOD;
}
}
}
}
return result;
}
};
class Solution:
def subsequencesWithMiddleMode(self, nums: List[int]) -> int:
MOD = 10**9 + 7
n = len(nums)
result = 0
def comb(n, k):
if k > n or k < 0:
return 0
if k == 0 or k == n:
return 1
res = 1
for i in range(k):
res = res * (n - i) // (i + 1)
return res
# 枚举中间位置
for mid in range(2, n - 2):
target = nums[mid]
# 统计左右两边元素出现次数
left_count = {}
for i in range(mid):
left_count[nums[i]] = left_count.get(nums[i], 0) + 1
right_count = {}
for i in range(mid + 1, n):
right_count[nums[i]] = right_count.get(nums[i], 0) + 1
left_target = left_count.get(target, 0)
right_target = right_count.get(target, 0)
# 枚举各种情况
for left_take in range(min(3, left_target + 1)):
for right_take in range(min(3, right_target + 1)):
if left_take + right_take > 4:
continue
left_remain = 2 - left_take
right_remain = 2 - right_take
if left_remain < 0 or right_remain < 0:
continue
total_target = 1 + left_take + right_take
# 计算方案数
ways = comb(left_target, left_take) * comb(right_target, right_take)
ways %= MOD
# 选择其他元素
if left_remain > 0:
left_others = mid - left_target
ways = ways * comb(left_others, left_remain) % MOD
if right_remain > 0:
right_others = (n - mid - 1) - right_target
ways = ways * comb(right_others, right_remain) % MOD
# 检查是否满足唯一众数条件（简化检查）
max_others = max(left_remain, right_remain) if left_remain > 0 or right_remain > 0 else 0
if total_target > max_others:
result = (result + ways) % MOD
return result
public class Solution {
public int SubsequencesWithMiddleMode(int[] nums) {
const int MOD = 1000000007;
int n = nums.Length;
long result = 0;
long Comb(int n, int k) {
if (k > n || k < 0) return 0;
if (k == 0 || k == n) return 1;
long res = 1;
for (int i = 0; i < k; i++) {
res = res * (n - i) / (i + 1);
}
return res;
}
// 枚举中间位置
for (int mid = 2; mid < n - 2; mid++) {
int target = nums[mid];
// 统计左右两边元素出现次数
var leftCount = new Dictionary<int, int>();
for (int i = 0; i < mid; i++) {
leftCount[nums[i]] = leftCount.GetValueOrDefault(nums[i], 0) + 1;
}
var rightCount = new Dictionary<int, int>();
for (int i = mid + 1; i < n; i++) {
rightCount[nums[i]] = rightCount.GetValueOrDefault(nums[i], 0) + 1;
}
int leftTarget = leftCount.GetValueOrDefault(target, 0);
int rightTarget = rightCount.GetValueOrDefault(target, 0);
// 枚举各种情况
for (int leftTake = 0; leftTake <= Math.Min(2, leftTarget); leftTake++) {
for (int rightTake = 0; rightTake <= Math.Min(2, rightTarget); rightTake++) {
int leftRemain = 2 - leftTake;
int rightRemain = 2 - rightTake;
if (leftRemain < 0 || rightRemain < 0) continue;
int totalTarget = 1 + leftTake + rightTake;
// 计算方案数
long ways = Comb(leftTarget, leftTake) * Comb(rightTarget, rightTake);
ways %= MOD;
// 选择其他元素
if (leftRemain > 0) {
int leftOthers = mid - leftTarget;
ways = ways * Comb(leftOthers, leftRemain) % MOD;
}
if (rightRemain > 0) {
int rightOthers = (n - mid - 1) - rightTarget;
ways = ways * Comb(rightOthers, rightRemain) % MOD;
}
// 检查是否满足唯一众数条件（简化检查）
int maxOthers = Math.Max(leftRemain, rightRemain);
if (leftRemain == 0 && rightRemain == 0) maxOthers = 0;
if (totalTarget > maxOthers) {
result = (result + ways) % MOD;
}
}
}
}
return (int)result;
}
}
var subsequencesWithMiddleMode = function(nums) {
const MOD = 1000000007;
const n = nums.length;
let result = 0;
// For each possible middle element at position i
for (let i = 2; i < n - 2; i++) {
const middle = nums[i];
// Count occurrences before and after position i
let leftCount = 0, rightCount = 0;
const leftElements = [];
const rightElements = [];
for (let j = 0; j < i; j++) {
leftElements.push(nums[j]);
if (nums[j] === middle) leftCount++;
}
for (let j = i + 1; j < n; j++) {
rightElements.push(nums[j]);
if (nums[j] === middle) rightCount++;
}
// Try all combinations of 2 elements from left and 2 from right
for (let l1 = 0; l1 < leftElements.length; l1++) {
for (let l2 = l1 + 1; l2 < leftElements.length; l2++) {
for (let r1 = 0; r1 < rightElements.length; r1++) {
for (let r2 = r1 + 1; r2 < rightElements.length; r2++) {
const subseq = [
leftElements[l1],
leftElements[l2],
middle,
rightElements[r1],
rightElements[r2]
];
// Count frequencies in the subsequence
const freq = {};
for (const num of subseq) {
freq[num] = (freq[num] || 0) + 1;
}
// Find the maximum frequency
const maxFreq = Math.max(...Object.values(freq));
// Check if middle element has unique mode (max frequency and is the only one with that frequency)
if (freq[middle] === maxFreq) {
const elementsWithMaxFreq = Object.keys(freq).filter(key => freq[key] === maxFreq);
if (elementsWithMaxFreq.length === 1) {
result = (result + 1) % MOD;
}
}
}
}
}
}
}
return result;
};
复杂度分析
| 指标 | 复杂度 |
|---|---|
| 时间 | - |
| 空间 | - |