likes
comments
collection
share

【面试高频题】难度 4/5，经典“逆序对”面试题

作者站长头像
站长
· 阅读数 67

题目描述

这是 LeetCode 上的 629. K个逆序对数组 ，难度为 困难。

Tag : 「序列 DP」、「前缀和」

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

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

由于答案可能很大，只需要返回 答案 mod 109 +710^9 + 7109 +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 个逆序对。

说明:

  •  n 的范围是 [1, 1000] 并且 k 的范围是 [0, 1000]。

序列 DP

从 nnn 和 kkk 数据范围均为 10310^3103 可以看出这是一道二维的动态规划题。

定义 f[i][j]f[i][j]f[i][j] 为考虑使用数值 [1,i][1,i][1,i]，凑成逆序对数量恰好为 jjj 的数组个数。

不失一般性的考虑 f[i][j]f[i][j]f[i][j] 该如何计算，对第 iii 个数（即数值为 iii 的数）所在位置进行讨论，共有 iii 种选择。

假设第 iii 个数所在位置为 kkk，由于数值 iii 为整个数组的最大值，因此数值 iii 与前面所有数均不形成逆序对，与后面的所有数均形成逆序对。因此与数值 iii 直接相关的逆向对的数量为 (i−1)−k(i - 1)- k(i−1)−k，由此也得出与 iii 不相关的逆序对数量为 j−(i−1−k)j - (i - 1 - k)j−(i−1−k)，而与 iii 不相关的逆序对数量由 f[i−1][x]f[i - 1][x]f[i−1][x] 可得出。

举个 🌰 帮助大家理解：

  • 当数值 iii 放置在下标为 000 的位置上，那么由数值 iii 产生的逆序对数量为 i−1i - 1i−1，总的逆序对数量为 jjj，因此由数值范围为 [1,i−1][1, i - 1][1,i−1]（与数值 iii 不相关）构成的逆序对数量为 j−(i−1)j - (i - 1)j−(i−1)，即 f[i−1][j−(i−1)]f[i - 1][j - (i - 1)]f[i−1][j−(i−1)]；

  • 当数值 iii 放置在下标为 111 的位置上，那么由数值 iii 产生的逆序对数量为 (i−1)−1(i - 1) - 1(i−1)−1，总的逆序对数量为 jjj，因此由数值范围为 [1,i−1][1, i - 1][1,i−1]（与数值 iii 不相关）构成的逆序对数量为 j−(i−1−1)j - (i - 1 - 1)j−(i−1−1)，即 f[i−1][j−(i−1−1)]f[i - 1][j - (i - 1 - 1)]f[i−1][j−(i−1−1)]；

    ...

  • 当数值 iii 放置在下标为 kkk 的位置上，那么由数值 iii 产生的逆序对数量为 (i−1)−k(i - 1) - k(i−1)−k，总的逆序对数量为 jjj，因此由数值范围为 [1,i−1][1, i - 1][1,i−1]（与数值 iii 不相关）构成的逆序对数量为 j−(i−1−k)j - (i - 1 - k)j−(i−1−k)，即 f[i−1][j−(i−1−k)]f[i - 1][j - (i - 1 - k)]f[i−1][j−(i−1−k)]。

综上，最终 f[i][j]f[i][j]f[i][j] 转移方程为（kkk 为数值 iii 放置的位置）：

f[i][j]=∑k=0i−1(f[i−1][j−(i−1−k)])f[i][j] = \sum_{k = 0}^{i - 1}(f[i - 1][j - (i - 1 - k)])f[i][j]=k=0∑i−1​(f[i−1][j−(i−1−k)])

共有 n∗kn * kn∗k 个状态，每个 f[i][j]f[i][j]f[i][j] 的计算需要枚举数值 iii 所在位置并进行累加，总的复杂度为 O(n2∗k)O(n^2 *k)O(n2∗k)，计算量为 10910^9109，会 TLE。

状态数量不可减少，考虑如何优化单个状态的转移过程。

不难发现 ∑k=0i−1(f[i−1][j−(i−1−k)])\sum_{k = 0}^{i - 1}(f[i - 1][j - (i - 1 - k)])∑k=0i−1​(f[i−1][j−(i−1−k)]) 部分为上一次转移结果 f[i−1][x]f[i - 1][x]f[i−1][x] 的某个前缀，可以使用前缀和数组进行优化，从而将计算单个状态的复杂度从 O(n)O(n)O(n) 降到 O(1)O(1)O(1)。

一些细节：为处理负数问题，我们可以在取模之前先加一次 mod；另外需要对 jjj 和 iii 的大小进行分情况讨论，防止数值 iii 放置的位置“过于靠前”导致组成逆序对的数量超过 jjj。

代码（P1P1P1 P2P2P2 分别为使用 long 和不使用 long）：

class Solution {
    int mod = (int)1e9+7;
    public int kInversePairs(int n, int k) {
        long[][] f = new long[n + 1][k + 1];
        long[][] sum = new long[n + 1][k + 1];
        f[1][0] = 1;
        Arrays.fill(sum[1], 1);
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                f[i][j] = j < i ? sum[i - 1][j] : sum[i - 1][j] - sum[i - 1][j - (i - 1) - 1];
                f[i][j] = (f[i][j] + mod) % mod;
                sum[i][j] = j == 0 ? f[i][j] : sum[i][j - 1] + f[i][j];
                sum[i][j] = (sum[i][j] + mod) % mod;
            }
        }
        return (int)f[n][k];
    }
}

class Solution {
    int mod = (int)1e9+7;
    public int kInversePairs(int n, int k) {
        int[][] f = new int[n + 1][k + 1];
        int[][] sum = new int[n + 1][k + 1];
        f[1][0] = 1;
        Arrays.fill(sum[1], 1);
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                f[i][j] = j < i ? sum[i - 1][j] : (sum[i - 1][j] - sum[i - 1][j - (i - 1) - 1] + mod) % mod;
                sum[i][j] = j == 0 ? f[i][j] : (sum[i][j - 1] + f[i][j]) % mod;
            }
        }
        return f[n][k];
    }
}
  • 时间复杂度：O(n×k)O(n \times k)O(n×k)
  • 空间复杂度：O(n×k)O(n \times k)O(n×k)

最后

这是我们「刷穿 LeetCode」系列文章的第 No.629 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉

转载自:https://juejin.cn/post/7218023263464915003
评论
请登录