跳转至

LeetCode: 629. K个逆序对数组

1、题目描述

给出两个整数 nk,找出所有包含从 1n 的数字,且恰好拥有 k 个逆序对的不同的数组的个数。

逆序对的定义如下:对于数组的第i个和第 j个元素,如果满i < ja[i] > a[j],则其为一个逆序对;否则不是。

由于答案可能很大,只需要返回 答案 mod 109 + 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 的范围是 [1, 1000] 并且 k 的范围是 [0, 1000]。

2、解题思路

​ 实际上,这个题目能够计算出来

​ 在1-n,有n个数字,最多有多少逆序对?

​ 如果全部是逆序,第一个元素,n-1个,第二个元素,n-2个,以此类推

​ 所以一共是n*(n-1)/2 个

实际上,我们可以使用动态规划来解决这个问题

n\k 0 1 2 3 4 5 6
0 1 0 0 0 0 0 0
1 1 0 0 0 0 0 0
2 1 1 0 0 0 0 0
3 1 2 2 1 0 0 0
4 1
5 1
6 1
7 1

假设n=5,已经知道n=4时的值,

那么添加一个5,可以得到下面的几种情况

xxxx5 不增加逆序对

xxx5x 增加1个逆序对

xx5xx 增加2个逆序对

x5xxx 增加3个逆序对

5xxxx 增加4个逆序对

那么,(5,k) = (4,k)+(4,k-1)+(4,k-2)+...+(4,k-(n-1))

不过,这样的计算量有点大,每一次,都要对前面多个进行加和计算

下面来进行一下优化

dp[n][k] = dp[n - 1][k] + dp[n - 1][k-1] + ... + dp[n - 1][k - n + 1]

用k+1代替k,得到:

dp[n][k+1] = dp[n - 1][k+1] + dp[n - 1][k] + ... + dp[n - 1][k + 1 - n + 1]

用第二个等式减去第一个等式得到:

dp[n][k+1] = dp[n][k] + dp[n - 1][k+1] - dp[n - 1][k - n + 1]

将k+1换回成k,可以得到:

dp[n][k] = dp[n][k-1] + dp[n - 1][k] - dp[n - 1][k - n]

第三项,只有当k>=n的时候,才会有值,所以分情况讨论即可

前面要求是10^9+7​, 直接计算出来,也就是1000000007

int kInversePairs(int n, int k) {
    int m = 1000000007;
    int dp[n + 1][k + 1];
    // 初始化, 所有的取0个逆序对的情况都只有一种
    for (int i = 0; i <= n; i++) {
        dp[i][0] = 1;
    }

    // 当有0个元素的时候,逆序对大于1的情况都是0
    for (int i = 1; i <= k; i++) {
        dp[0][i] = 0;
    }

    // 开始为计算所有的dp元素
    for (int row_n = 1; row_n <= n; row_n++) {
        for (int col_k = 1; col_k <= k; col_k++) {
            dp[row_n][col_k] = (dp[row_n - 1][col_k] + dp[row_n][col_k - 1]) % m;
            if (col_k >= row_n) {
                dp[row_n][col_k] = (dp[row_n][col_k] - dp[row_n - 1][col_k - row_n] + m) % m;
            }
        }
    }
    return dp[n][k];
}

​ 这里有一点需要注意的就是,