2025-01-23：统计逆序对的数目。用go语言，给定一个整数 n 和一个二维数组 requirements，其中每个元素 r

福大大架构师每日一题

发布于 2025-01-23 19:46:57

3500

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2025-01-23：统计逆序对的数目。用go语言，给定一个整数 n 和一个二维数组 requirem)ents，其中每个元素 requirements[i] = [endi, cnti] 表示在要求中末尾的下标以及逆序对的数量。

在一个整数数组 nums 中，如果存在一个下标对 (i, j)，使得 i < j 且 nums[i] > nums[j]，则称这对 (i, j) 为逆序对。

任务是返回所有可能的数组排列 perm = [0, 1, 2, ..., n - 1] 的数量，使得对于所有的 requirements，都满足 perm[0..endi] 中恰好有 cnti 个逆序对。

由于结果可能会非常大，请将结果对 1000000007 取余后返回。

2 <= n <= 300。

1 <= requirements.length <= n。

requirements[i] = [endi, cnti]。

0 <= endi <= n - 1。

0 <= cnti <= 400。

输入保证至少有一个 i 满足 endi == n - 1 。

输入保证所有的 endi 互不相同。

输入：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 个。

答案2025-01-23：

chatgpt[1]

题目来自leetcode3193。

大体步骤如下：

1.定义常量 MOD，表示取余值为 1e9 + 7。

2.编写函数 numberOfPermutations(n, requirements) 来计算符合要求的排列数量。

3.初始化一个要求映射 reqMap，记录每个末尾下标及其逆序对数量的要求。同时找出最大的逆序对数量 maxCnt。

4.构建动态规划数组 dp，用于存储计算结果，其中 dp[i][j] 表示前 i 个数中逆序对数量为 j 的排列数。

5.定义递归函数 dfs(end, cnt) 来计算符合要求的排列数量。

6.在 dfs 函数中，首先处理边界情况，然后根据当前位置是否存在逆序对要求进行不同的处理。

7.在主函数 main 中，给定 n = 3 和 requirements = [[2,2],[0,0]]，调用 numberOfPermutations 函数计算结果并打印输出。

总的时间复杂度：

• 针对每个位置及逆序对情况进行递归计算，时间复杂度为 O(n * maxCnt)。
• 最终结果取模操作的时间复杂度为 O(1)。

总的额外空间复杂度：

• 使用了 reqMap 来存储逆序对的要求，空间复杂度为 O(n)。
• 动态规划数组 dp 使用了二维数组来存储计算结果，空间复杂度为 O(n * maxCnt)。

因此，总的时间复杂度为 O(n * maxCnt)，总的额外空间复杂度为 O(n * maxCnt)。

Go完整代码如下：

package main

import (
    "fmt"
)

const MOD int64 = 1e9 + 7

func numberOfPermutations(n int, requirements [][]int)int {
    reqMap := make(map[int]int)
    reqMap[0] = 0
    maxCnt := 0
    for _, req := range requirements {
        reqMap[req[0]] = req[1]
        if req[1] > maxCnt {
            maxCnt = req[1]
        }
    }
    if reqMap[0] != 0 {
        return0
    }

    dp := make([][]int64, n)
    for i := range dp {
        dp[i] = make([]int64, maxCnt + 1)
        for j := range dp[i] {
            dp[i][j] = -1
        }
    }

    var dfs func(int, int)int64
    dfs = func(end, cnt int)int64 {
        if cnt < 0 {
            return0
        }
        if end == 0 {
            return1
        }
        if dp[end][cnt] != -1 {
            return dp[end][cnt]
        }
        if r, exists := reqMap[end - 1]; exists {
            if r <= cnt && cnt <= end + r {
                dp[end][cnt] = dfs(end - 1, r)
                return dp[end][cnt]
            }
            return0
        } else {
            if cnt > end {
                dp[end][cnt] = (dfs(end, cnt - 1) - dfs(end - 1, cnt - 1 - end) + dfs(end - 1, cnt) + MOD) % MOD
            } else {
                dp[end][cnt] = (dfs(end, cnt - 1) + dfs(end - 1, cnt)) % MOD
            }
            return dp[end][cnt]
        }
    }

    returnint(dfs(n - 1, reqMap[n - 1]))
}

func main() {
    n := 3
    requirements := [][]int{{2,2},{0,0}}
    result := numberOfPermutations(n,requirements)
    fmt.Println(result)
}

Rust完整代码如下：

use std::collections::HashMap;

const MOD: i64 = 1_000_000_007;

fnnumber_of_permutations(n: usize, requirements: Vec<Vec<i32>>) ->i64 {
    letmut req_map: HashMap<i32, i32> = HashMap::new();
    req_map.insert(0, 0);
    letmut max_cnt = 0;

    forreqin requirements {
        req_map.insert(req[0], req[1]);
        if req[1] > max_cnt {
            max_cnt = req[1];
        }
    }

    if *req_map.get(&0).unwrap() != 0 {
        return0;
    }

    letmut dp = vec![vec![-1; (max_cnt + 1) asusize]; n];

    fndfs(end: usize, cnt: i32, req_map: &HashMap<i32, i32>, dp: &mutVec<Vec<i64>>) ->i64 {
        if cnt < 0 {
            return0;
        }
        if end == 0 {
            return1;
        }
        if dp[end][cnt asusize] != -1 {
            return dp[end][cnt asusize];
        }
        ifletSome(&r) = req_map.get(&(end asi32 - 1)) {
            if r <= cnt && cnt <= end asi32 + r {
                dp[end][cnt asusize] = dfs(end - 1, r, req_map, dp);
            } else {
                return0;
            }
        } else {
            if cnt > end asi32 {
                dp[end][cnt asusize] = (dfs(end, cnt - 1, req_map, dp) - 
                                          dfs(end - 1, cnt - 1 - end asi32, req_map, dp) + 
                                          dfs(end - 1, cnt, req_map, dp) + MOD) % MOD;
            } else {
                dp[end][cnt asusize] = (dfs(end, cnt - 1, req_map, dp) + 
                                          dfs(end - 1, cnt, req_map, dp)) % MOD;
            }
        }
        dp[end][cnt asusize]
    }

    returndfs(n - 1, *req_map.get(&(n asi32 - 1)).unwrap(), &req_map, &mut dp);
}

fnmain() {
    letn = 3;
    letrequirements = vec![vec![2, 2], vec![0, 0]];
    letresult = number_of_permutations(n, requirements);
    println!("{}", result);
}

Python完整代码如下：

# -*-coding:utf-8-*-

MOD = 10**9 + 7

defnumber_of_permutations(n, requirements):
    req_map = {0: 0}
    max_cnt = 0

    for req in requirements:
        req_map[req[0]] = req[1]
        if req[1] > max_cnt:
            max_cnt = req[1]

    if req_map[0] != 0:
        return0

    # 初始化动态规划表
    dp = [[-1] * (max_cnt + 1) for _ inrange(n)]

    defdfs(end, cnt):
        if cnt < 0:
            return0
        if end == 0:
            return1
        if dp[end][cnt] != -1:
            return dp[end][cnt]

        if end - 1in req_map:
            r = req_map[end - 1]
            if r <= cnt <= end + r:
                dp[end][cnt] = dfs(end - 1, r)
                return dp[end][cnt]
            return0
        else:
            if cnt > end:
                dp[end][cnt] = (dfs(end, cnt - 1) - dfs(end - 1, cnt - 1 - end) + dfs(end - 1, cnt)) % MOD
            else:
                dp[end][cnt] = (dfs(end, cnt - 1) + dfs(end - 1, cnt)) % MOD
            return dp[end][cnt]

    returnint(dfs(n - 1, req_map[n - 1]))

defmain():
    n = 3
    requirements = [[2, 2], [0, 0]]
    result = number_of_permutations(n, requirements)
    print(result)

if __name__ == "__main__":
    main()