262数组子序列的排列个数

题解

题目要求计算数组中满足特定条件的子序列数量。具体来说，子序列必须是从 1 到 m 的完整排列，且按升序排列。

解题思路

1. 计数元素频次：

   使用 Counter 统计数组中每个元素出现的次数。这样可以快速获取每个数字出现的数量。

2. 迭代构建排列：

   从 1 开始，依次检查每个数字 i 是否存在于数组中（即 cnt[i] > 0）。

   • 如果存在，当前排列长度为 i，可以选择的方式数为 cnt[i]。

   • 将当前选择方式数累乘到一个累积变量 f 中，表示构建长度为 i 的排列的总方式数。

   • 将 f 加到最终结果 res 中。

   • 一旦发现某个数字 i 在数组中不存在（即 cnt[i] == 0），说明无法继续构建更长的排列，循环终止。

示例分析

以样例 1 为例：

• 数组 [1, 1, 5, 2, 3, 4] 中元素计数为 {1:2, 5:1, 2:1, 3:1, 4:1}。

• 依次计算：

  • m=1:

    cnt[1] = 2 → f = 2 → res = 2

  • m=2:

    cnt[2] = 1 → f = 2 * 1 = 2 → res = 4

  • m=3:

    cnt[3] = 1 → f = 2 * 1 * 1 = 2 → res = 6

  • m=4:

    cnt[4] = 1 → f = 2 * 1 * 1 * 1 = 2 → res = 8

  • m=5:

    cnt[5] = 1 → f = 2 * 1 * 1 * 1 * 1 = 2 → res = 10

  • m=6:

    cnt[6] = 0 → 终止

• 最终结果为 10。

代码

from collections import Counter
def solution(n: int, a: list) -> int:
    cnt = Counter(a)
    res = 0
    f = 1
    for i in range(1, n + 1):
        if cnt[i] == 0:
            break
        f *= cnt[i]
        res += f

    return res

if __name__ == '__main__':
    print(solution(6, [1, 1, 5, 2, 3, 4]) == 10)
    print(solution(5, [1, 2, 3, 4, 5]) == 5)
    print(solution(7, [1, 3, 5, 2, 4, 6, 7]) == 7)
    print(solution(9, [5,3,2,1,3,5,6,8,8]) == 4)
    print(solution(5, [1,1,2,3,3]))

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组长度，用于统计元素频次。
• 空间复杂度：O(n)，用于存储元素频次。