3193. 统计逆序对的数目 - 力扣（LeetCode）

调试中...

题目描述

题解

提交记录

代码

测试用例

测试结果

3193. 统计逆序对的数目

困难

相关企业

提示

给你一个整数 n 和一个二维数组 requirements ，其中 requirements[i] = [end_i, cnt_i] 表示这个要求中的末尾下标和 逆序对 的数目。

整数数组 nums 中一个下标对 (i, j) 如果满足以下条件，那么它们被称为一个 逆序对 ：

i < j 且 nums[i] > nums[j]

请你返回 [0, 1, 2, ..., n - 1] 的 perm 的数目，满足对所有的 requirements[i] 都满足 perm[0..end_i] 中恰好有 cnt_i 个逆序对。

由于答案可能会很大，将它对 10⁹ + 7 取余后返回。

示例 1：

输入：n = 3, requirements = [[2,2],[0,0]]

输出：2

解释：

两个排列为：

[2, 0, 1]
- 前缀 [2, 0, 1] 的逆序对为 (0, 1) 和 (0, 2) 。
- 前缀 [2] 的逆序对数目为 0 个。
[1, 2, 0]
- 前缀 [1, 2, 0] 的逆序对为 (0, 2) 和 (1, 2) 。
- 前缀 [1] 的逆序对数目为 0 个。

示例 2：

输入：n = 3, requirements = [[2,2],[1,1],[0,0]]

输出：1

解释：

唯一满足要求的排列是 [2, 0, 1] ：

前缀 [2, 0, 1] 的逆序对为 (0, 1) 和 (0, 2) 。
前缀 [2, 0] 的逆序对为 (0, 1) 。
前缀 [2] 的逆序对数目为 0 。

示例 3：

输入：n = 2, requirements = [[0,0],[1,0]]

输出：1

解释：

唯一满足要求的排列为 [0, 1] ：

前缀 [0] 的逆序对数目为 0 。
前缀 [0, 1] 的逆序对为 (0, 1) 。

提示：

2 <= n <= 300
1 <= requirements.length <= n
requirements[i] = [end_i, cnt_i]
0 <= end_i <= n - 1
0 <= cnt_i <= 400
输入保证至少有一个 i 满足 end_i == n - 1 。
输入保证所有的 end_i 互不相同。

通过次数

10.5K

提交次数

17.8K

通过率

58.6%

相关企业

提示 1

Let dp[i][j] denote the number of arrays of length i with j inversions.

提示 2

dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] + … + dp[i - 1][0].

提示 3

dp[i][j] = 0 if for some x, requirements[x][0] == i and requirements[x][1] != j.

相似题目

K 个逆序对数组

困难

贡献者

0 人在线

行 1，列 1

运行和提交代码需要登录

n =

requirements =

[[2,2],[0,0]]

[[2,2],[1,1],[0,0]]

[[0,0],[1,0]]

Source

FindHeaderBarSize

FindTabBarSize

FindBorderBarSize