0629：K 个逆序对数组（★★）

2016-09-20 约 493 字预计阅读 1 分钟次阅读

力扣第 629 题

题目

对于一个整数数组 nums，逆序对是一对满足 0 <= i < j < nums.length 且 nums[i] > nums[j]的整数对 [i, j] 。

给你两个整数 n 和 k，找出所有包含从 1 到 n 的数字，且恰好拥有 k 个 逆序对 的不同的数组的个数。由于答案可能很大，只需要返回对 10⁹ + 7 取余的结果。

示例 1：

输入：n = 3, k = 0
输出：1
解释：
只有数组 [1,2,3] 包含了从1到3的整数并且正好拥有 0 个逆序对。

示例 2：

输入：n = 3, k = 1
输出：2
解释：
数组 [1,3,2] 和 [2,1,3] 都有 1 个逆序对。

提示：

1 <= n <= 1000
0 <= k <= 1000

相似问题：

3193：统计逆序对的数目（2266 分）

分析

#1

先考虑 n 放哪，假如 n 放到位置 i，包含 n 的逆序对有 n-i-1，转为子问题：1 到 n-1 的排列中恰好 k-(n-i-1) 个逆序对的个数
n 产生的逆序对个数范围为 [0,n-1]
令 f[i][j] 代表 1 到 i 的排列中恰好 j 个逆序对的个数，即可递推： f[i][j] = sum(f[i-1][j-a] for a in range(i) if j>=a)
显然递推式可以用前缀和优化
还可以用滚动数组将 f 优化为一维数组

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


class Solution:
    def kInversePairs(self, n: int, k: int) -> int:
        mod = 10**9+7
        f = [1]+[0]*k
        for i in range(2,n+1):
            g = list(accumulate(f))
            for j in range(k+1):
                f[j] = g[j]-(g[j-i] if j>=i else 0)
                f[j] %= mod
        return f[-1]

303 ms

#2

还可以只用 f 数组，注意遍历顺序即可。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


class Solution:
    def kInversePairs(self, n: int, k: int) -> int:
        mod = 10**9+7
        f = [1]+[0]*k
        for i in range(2,n+1):
            for j in range(1,k+1):
                f[j] = (f[j]+f[j-1])%mod
            for j in range(k,i-1,-1):
                f[j] = (f[j]-f[j-i])%mod
        return f[-1]

251 ms

目录

0629：K 个逆序对数组（★★）

题目

分析

#1

#2

解答