LeetCode 629. K 个逆序对数组题目原文题号629标题K 个逆序对数组对于一个整数数组 nums逆序对是一对满足0 i j nums.length且nums[i] nums[j]的整数对[i, j]。给你两个整数 n 和 k找出所有包含从 1 到 n 的数字且恰好拥有 k 个逆序对的不同的数组的个数。由于答案可能很大只需要返回对109710^971097取余的结果。约束1≤n≤10001 \le n \le 10001≤n≤10000≤k≤10000 \le k \le 10000≤k≤1000示例1输入n 3, k 0 输出1 解释只有 [1,2,3]0个逆序对示例2输入n 3, k 1 输出2 解释两个排列[1,3,2]、[2,1,3]都恰好1个逆序对费曼学习法讲解破解思路通俗化像给小白讲课1. 先搞懂问题本质我们不是要列出所有排列而是计数1~n 的全排列里面有多少个排列刚好存在 k 对逆序对。逆序对一句话前面的数 后面的数。比如 [1,3,2]i1,j2321组逆序对。暴力思路生成全部n!个排列逐个统计逆序对数量。❌ 直接废掉n1000阶乘是天文数字完全不可能。所以必须动态规划。2. DP状态定义核心dp[i][j]dp[i][j]dp[i][j]使用数字1~i构成排列恰好有 j 个逆序对的排列总数关键观察费曼重点假设我们已经知道i-1个数所有排列方案dp[i-1][...]。现在插入最大数字i到 1~i-1 的排列中插在最后面i是最大不会产生任何逆序对新增0个逆序对倒数第2位置i会比后面1个数大 →新增1个逆序对倒数第3位置i会比后面2个数大 →新增2个逆序对……插到最前面i后面一共i-1个数 →新增 i-1 个逆序对✅ 结论插入数字i新增逆序对可以是0,1,2,...,i-1。要凑 j 个逆序对原来 i-1 个数的逆序对数可以是 j, j-1, j-2 … 一直到j-(i-1)递推公式dp[i][j]∑xmax(0,j−(i−1))jdp[i−1][x]dp[i][j]\sum_{x\max(0,j-(i-1))}^{j} dp[i-1][x]dp[i][j]xmax(0,j−(i−1))∑jdp[i−1][x]意思就是dp[i][j] dp[i-1][j] dp[i-1][j-1] ... dp[i-1][j-(i-1)]问题直接求和会超时n和k都是1000。如果每次j都循环累加i项复杂度O(n2k)O(n^2k)O(n2k)会超时。 优化手段前缀和数组前缀和 pre[j] dp[i−1][0]dp[i−1][1]...dp[i−1][j−1]dp[i-1][0]dp[i-1][1]...dp[i-1][j-1]dp[i−1][0]dp[i−1][1]...dp[i−1][j−1]区间和dp[i-1][a ... b] pre[b1] - pre[a]这样每次求区间和变成 O(1)总复杂度 O(n*k)可以通过。空间继续优化二维数组 dp[i][j]但计算i只依赖i-1那一行不需要保存全部行。我们只用一维数组滚动更新只保留上一轮的dp数组节省内存。边界条件dp[1][0]1dp[1][0] 1dp[1][0]1只有数字1排列只有[1]逆序对0方案1种。dp[1][j0]0dp[1][j0]0dp[1][j0]0单个数字不可能产生大于0的逆序对。MOD 109710^971097减法时要加上MOD再取模防止负数。Python 完整代码每行详尽注释一维滚动数组 前缀和优化classSolution:defkInversePairs(self,n:int,k:int)-int:# 模数题目要求答案对10^97取模MOD10**97# dp数组dp[j]代表当前i个数恰好j个逆序对的排列数量# 初始化i1只有数字1只有0逆序对的方案1其余都是0dp[0]*(k1)dp[0]1# i从2遍历到ni代表当前我们要加入数字i构造1~i的排列foriinrange(2,n1):# 构造上一轮dp数组的前缀和数组pre# pre[0]0; pre[t] dp[0]dp[1]...dp[t-1]pre[0]*(k2)fortinrange(k1):# 前缀累加每次取模防止数值溢出pre[t1](pre[t]dp[t])%MOD# 新建本轮dp数组存储i个数的结果new_dp[0]*(k1)# j遍历所有可能逆序对数量0~kforjinrange(k1):# 左边界最多往前取i-1项不能小于0leftmax(0,j-(i-1))# 区间求和 dp[i-1][left ... j] pre[j1] - pre[left]total(pre[j1]-pre[left])%MOD new_dp[j]total# 更新dp为本轮结果下一轮i1使用dpnew_dp# 返回n个数恰好k逆序对的方案数再取一次模保证正数returndp[k]%MOD简化测试调用代码# 测试样例solSolution()print(sol.kInversePairs(3,0))#输出1print(sol.kInversePairs(3,1))#输出2print(sol.kInversePairs(4,2))#输出5二维DP版本方便理解不空间优化同样带注释classSolution:defkInversePairs(self,n:int,k:int)-int:MOD10**97# dp[i][j]1~ij逆序对i从1~nj从0~kdp[[0]*(k1)for_inrange(n1)]# base case i1dp[1][0]1foriinrange(2,n1):# 构造i-1行的前缀和pre[0]*(k2)fortinrange(k1):pre[t1](pre[t]dp[i-1][t])%MODforjinrange(k1):leftmax(0,j-(i-1))dp[i][j](pre[j1]-pre[left])%MODreturndp[n][k]%MOD二维版本直观但空间 O(nk)n,k1000时占用100万空间Python能跑一维滚动数组把空间压缩为O(k)面试推荐一维版本。应用场景举例场景1密码/排列组合计数信息安全某些加密算法会基于置换排列做混淆需要统计满足指定逆序对数量的置换总数评估密钥空间大小。这道题就是这类置换计数的基础模型。场景2排序算法复杂度分析逆序对数量是衡量数组乱序程度的指标冒泡排序交换次数数组逆序对总数。当需要统计长度n的随机排列中有多少种排列刚好有k次冒泡交换就等价于本题。场景3统计学、概率模拟生成随机排列求“恰好k逆序对”的概率 kInversePairs(n,k) / n!用于蒙特卡洛模拟分析排列分布。场景4竞赛算法基础模板这道题是DP前缀和优化的经典模板题。很多组合计数DP子数组求和、滑动窗口求和优化DP都复用这套思路DP状态依赖一段连续区间的和用前缀和降复杂度。补充费曼自检一句话总结每次把最大数字i插入前面i-1的排列最多新增i-1个逆序对dp[i][j]等于前一行一段连续区间求和前缀和把区间求和从O(i)压到O(1)一维滚动数组节省内存结果模109710^971097。
LeetCode 629. K 个逆序对数组
LeetCode 629. K 个逆序对数组题目原文题号629标题K 个逆序对数组对于一个整数数组 nums逆序对是一对满足0 i j nums.length且nums[i] nums[j]的整数对[i, j]。给你两个整数 n 和 k找出所有包含从 1 到 n 的数字且恰好拥有 k 个逆序对的不同的数组的个数。由于答案可能很大只需要返回对109710^971097取余的结果。约束1≤n≤10001 \le n \le 10001≤n≤10000≤k≤10000 \le k \le 10000≤k≤1000示例1输入n 3, k 0 输出1 解释只有 [1,2,3]0个逆序对示例2输入n 3, k 1 输出2 解释两个排列[1,3,2]、[2,1,3]都恰好1个逆序对费曼学习法讲解破解思路通俗化像给小白讲课1. 先搞懂问题本质我们不是要列出所有排列而是计数1~n 的全排列里面有多少个排列刚好存在 k 对逆序对。逆序对一句话前面的数 后面的数。比如 [1,3,2]i1,j2321组逆序对。暴力思路生成全部n!个排列逐个统计逆序对数量。❌ 直接废掉n1000阶乘是天文数字完全不可能。所以必须动态规划。2. DP状态定义核心dp[i][j]dp[i][j]dp[i][j]使用数字1~i构成排列恰好有 j 个逆序对的排列总数关键观察费曼重点假设我们已经知道i-1个数所有排列方案dp[i-1][...]。现在插入最大数字i到 1~i-1 的排列中插在最后面i是最大不会产生任何逆序对新增0个逆序对倒数第2位置i会比后面1个数大 →新增1个逆序对倒数第3位置i会比后面2个数大 →新增2个逆序对……插到最前面i后面一共i-1个数 →新增 i-1 个逆序对✅ 结论插入数字i新增逆序对可以是0,1,2,...,i-1。要凑 j 个逆序对原来 i-1 个数的逆序对数可以是 j, j-1, j-2 … 一直到j-(i-1)递推公式dp[i][j]∑xmax(0,j−(i−1))jdp[i−1][x]dp[i][j]\sum_{x\max(0,j-(i-1))}^{j} dp[i-1][x]dp[i][j]xmax(0,j−(i−1))∑jdp[i−1][x]意思就是dp[i][j] dp[i-1][j] dp[i-1][j-1] ... dp[i-1][j-(i-1)]问题直接求和会超时n和k都是1000。如果每次j都循环累加i项复杂度O(n2k)O(n^2k)O(n2k)会超时。 优化手段前缀和数组前缀和 pre[j] dp[i−1][0]dp[i−1][1]...dp[i−1][j−1]dp[i-1][0]dp[i-1][1]...dp[i-1][j-1]dp[i−1][0]dp[i−1][1]...dp[i−1][j−1]区间和dp[i-1][a ... b] pre[b1] - pre[a]这样每次求区间和变成 O(1)总复杂度 O(n*k)可以通过。空间继续优化二维数组 dp[i][j]但计算i只依赖i-1那一行不需要保存全部行。我们只用一维数组滚动更新只保留上一轮的dp数组节省内存。边界条件dp[1][0]1dp[1][0] 1dp[1][0]1只有数字1排列只有[1]逆序对0方案1种。dp[1][j0]0dp[1][j0]0dp[1][j0]0单个数字不可能产生大于0的逆序对。MOD 109710^971097减法时要加上MOD再取模防止负数。Python 完整代码每行详尽注释一维滚动数组 前缀和优化classSolution:defkInversePairs(self,n:int,k:int)-int:# 模数题目要求答案对10^97取模MOD10**97# dp数组dp[j]代表当前i个数恰好j个逆序对的排列数量# 初始化i1只有数字1只有0逆序对的方案1其余都是0dp[0]*(k1)dp[0]1# i从2遍历到ni代表当前我们要加入数字i构造1~i的排列foriinrange(2,n1):# 构造上一轮dp数组的前缀和数组pre# pre[0]0; pre[t] dp[0]dp[1]...dp[t-1]pre[0]*(k2)fortinrange(k1):# 前缀累加每次取模防止数值溢出pre[t1](pre[t]dp[t])%MOD# 新建本轮dp数组存储i个数的结果new_dp[0]*(k1)# j遍历所有可能逆序对数量0~kforjinrange(k1):# 左边界最多往前取i-1项不能小于0leftmax(0,j-(i-1))# 区间求和 dp[i-1][left ... j] pre[j1] - pre[left]total(pre[j1]-pre[left])%MOD new_dp[j]total# 更新dp为本轮结果下一轮i1使用dpnew_dp# 返回n个数恰好k逆序对的方案数再取一次模保证正数returndp[k]%MOD简化测试调用代码# 测试样例solSolution()print(sol.kInversePairs(3,0))#输出1print(sol.kInversePairs(3,1))#输出2print(sol.kInversePairs(4,2))#输出5二维DP版本方便理解不空间优化同样带注释classSolution:defkInversePairs(self,n:int,k:int)-int:MOD10**97# dp[i][j]1~ij逆序对i从1~nj从0~kdp[[0]*(k1)for_inrange(n1)]# base case i1dp[1][0]1foriinrange(2,n1):# 构造i-1行的前缀和pre[0]*(k2)fortinrange(k1):pre[t1](pre[t]dp[i-1][t])%MODforjinrange(k1):leftmax(0,j-(i-1))dp[i][j](pre[j1]-pre[left])%MODreturndp[n][k]%MOD二维版本直观但空间 O(nk)n,k1000时占用100万空间Python能跑一维滚动数组把空间压缩为O(k)面试推荐一维版本。应用场景举例场景1密码/排列组合计数信息安全某些加密算法会基于置换排列做混淆需要统计满足指定逆序对数量的置换总数评估密钥空间大小。这道题就是这类置换计数的基础模型。场景2排序算法复杂度分析逆序对数量是衡量数组乱序程度的指标冒泡排序交换次数数组逆序对总数。当需要统计长度n的随机排列中有多少种排列刚好有k次冒泡交换就等价于本题。场景3统计学、概率模拟生成随机排列求“恰好k逆序对”的概率 kInversePairs(n,k) / n!用于蒙特卡洛模拟分析排列分布。场景4竞赛算法基础模板这道题是DP前缀和优化的经典模板题。很多组合计数DP子数组求和、滑动窗口求和优化DP都复用这套思路DP状态依赖一段连续区间的和用前缀和降复杂度。补充费曼自检一句话总结每次把最大数字i插入前面i-1的排列最多新增i-1个逆序对dp[i][j]等于前一行一段连续区间求和前缀和把区间求和从O(i)压到O(1)一维滚动数组节省内存结果模109710^971097。
