下面给你LeetCode 3193「统计逆序对的数目」的 Rust 实现思路与 Java / TS 版本一致但使用了Rust 风格的前缀和 滚动数组在保证可读性的同时尽量节省内存。✅ Rust 实现推荐impl Solution { pub fn number_of_permutations(n: i32, requirements: VecVeci32) - i32 { const MOD: i64 1_000_000_007; let n n as usize; // 将约束存入 HashMap let mut req std::collections::HashMap::new(); for r in requirements { req.insert(r[0] as usize, r[1] as i64); } // 检查第一个位置 if req.get(0).map_or(false, |v| v ! 0) { return 0; } // 最大逆序对数 let max_inv n * (n - 1) / 2; // dp[j] 表示当前长度排列中逆序对数为 j 的方案数 let mut dp vec![0i64; max_inv 1]; dp[0] 1; for i in 1..n { // 前缀和 let mut prefix vec![0i64; max_inv 1]; prefix[0] dp[0]; for j in 1..max_inv { prefix[j] (prefix[j - 1] dp[j]) % MOD; } // 计算新的 dp let mut new_dp vec![0i64; max_inv 1]; for j in 0..max_inv { let left j.saturating_sub(i - 1); let right j; let mut sum prefix[right]; if left 0 { sum (sum - prefix[left - 1] MOD) % MOD; } new_dp[j] sum; } // 处理约束 if let Some(cnt) req.get((i - 1)) { for j in 0..max_inv { if j as i64 ! cnt { new_dp[j] 0; } } } dp new_dp; } // 最终结果 if let Some(cnt) req.get((n - 1)) { dp[cnt as usize] as i32 } else { (dp.iter().sum::i64() % MOD) as i32 } } } 核心思路Rust 版状态定义dp[j] 当前长度的排列中逆序对数为 j 的方案数转移方程插入数字i时最多新增i-1个逆序对dp_new[j] Σ dp_old[j-k], 0 ≤ k ≤ i-1 用前缀和优化区间求和。⏱️ 复杂度分析项目复杂度时间O(n²)空间O(n²) → 滚动数组优化为 O(n²)LeetCode 官方数据范围n ≤ 500完全可接受。✅ 示例测试fn main() { let res Solution::number_of_permutations( 3, vec![vec![2, 2]], ); println!({}, res); // 输出 1 } Rust 常见坑提醒✅ 使用i64防止溢出✅saturating_sub替代max(0, j-i)✅ 每次 DP 后立即清零不满足约束的状态✅% MOD必须加在每一步累加上如果你愿意我可以帮你✅进一步压缩空间单数组 反向遍历✅写#[test]单元测试✅对比 Rust / Java / TypeScript 性能✅手推 DP 表帮助你理解转移过程随时告诉我
元宝 DeepSeek LeetCode 3193. 统计逆序对的数目 Rust实现
发布时间：2026/6/14 20:56:02
下面给你LeetCode 3193「统计逆序对的数目」的 Rust 实现思路与 Java / TS 版本一致但使用了Rust 风格的前缀和 滚动数组在保证可读性的同时尽量节省内存。✅ Rust 实现推荐impl Solution { pub fn number_of_permutations(n: i32, requirements: VecVeci32) - i32 { const MOD: i64 1_000_000_007; let n n as usize; // 将约束存入 HashMap let mut req std::collections::HashMap::new(); for r in requirements { req.insert(r[0] as usize, r[1] as i64); } // 检查第一个位置 if req.get(0).map_or(false, |v| v ! 0) { return 0; } // 最大逆序对数 let max_inv n * (n - 1) / 2; // dp[j] 表示当前长度排列中逆序对数为 j 的方案数 let mut dp vec![0i64; max_inv 1]; dp[0] 1; for i in 1..n { // 前缀和 let mut prefix vec![0i64; max_inv 1]; prefix[0] dp[0]; for j in 1..max_inv { prefix[j] (prefix[j - 1] dp[j]) % MOD; } // 计算新的 dp let mut new_dp vec![0i64; max_inv 1]; for j in 0..max_inv { let left j.saturating_sub(i - 1); let right j; let mut sum prefix[right]; if left 0 { sum (sum - prefix[left - 1] MOD) % MOD; } new_dp[j] sum; } // 处理约束 if let Some(cnt) req.get((i - 1)) { for j in 0..max_inv { if j as i64 ! cnt { new_dp[j] 0; } } } dp new_dp; } // 最终结果 if let Some(cnt) req.get((n - 1)) { dp[cnt as usize] as i32 } else { (dp.iter().sum::i64() % MOD) as i32 } } } 核心思路Rust 版状态定义dp[j] 当前长度的排列中逆序对数为 j 的方案数转移方程插入数字i时最多新增i-1个逆序对dp_new[j] Σ dp_old[j-k], 0 ≤ k ≤ i-1 用前缀和优化区间求和。⏱️ 复杂度分析项目复杂度时间O(n²)空间O(n²) → 滚动数组优化为 O(n²)LeetCode 官方数据范围n ≤ 500完全可接受。✅ 示例测试fn main() { let res Solution::number_of_permutations( 3, vec![vec![2, 2]], ); println!({}, res); // 输出 1 } Rust 常见坑提醒✅ 使用i64防止溢出✅saturating_sub替代max(0, j-i)✅ 每次 DP 后立即清零不满足约束的状态✅% MOD必须加在每一步累加上如果你愿意我可以帮你✅进一步压缩空间单数组 反向遍历✅写#[test]单元测试✅对比 Rust / Java / TypeScript 性能✅手推 DP 表帮助你理解转移过程随时告诉我
