K 反转对数组

2025年2月7日 | 阅读6分钟

问题陈述

逆序对是一个偶数对 [i,j]，其中数组的第一个元素满足 i < j < nums.length 且 nums[i] > nums[j] 为真。如果程序的输入是两个整数 n 和 k，则返回包含从 1 到 n 的数字、且恰好有 k 个逆序对的不同数组的数量。你找到的答案可能相当大，因此，你应该将其对 10^9 + 7 取模。

示例 1

输入： n = 3, k = 0

输出： 1

说明

n = 3，这意味着我们有从 1 到 3 的整数。

k = 0，表示我们需要找到恰好有 0 个逆序对的数组。

现在，让我们列出所有可能用从 1 到 3 的数字构成的长度为 3（因为 n = 3）的数组。

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

现在，让我们检查这些数组各自有多少个逆序对。

[1, 2, 3] - 0 个逆序对
[1, 3, 2] - 1 个逆序对 ([3, 2])
[2, 1, 3] - 1 个逆序对 ([2, 1])
[2, 3, 1] - 1 个逆序对 ([2, 1])
[3, 1, 2] - 2 个逆序对 ([3, 1], [3, 2])
[3, 2, 1] - 3 个逆序对 ([3, 2], [3, 1], [2, 1])

根据给定条件，只有第一个数组（[1, 2, 3]）恰好有 0 个逆序对，这正是我们所寻找的。因此，只有一个数组满足要求；所以输出为 1。

示例 2

输入： n = 3, k = 1

输出：2

说明

n = 3，意味着我们有从 1 到 3 的整数。

k = 1，表示我们需要找到恰好有 1 个逆序对的数组。

现在，让我们列出所有可能用从 1 到 3 的数字构成的长度为 3 的数组。

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

现在，让我们计算这些数组各自的逆序对数量。

[1, 2, 3] - 0 个逆序对
[1, 3, 2] - 1 个逆序对 ([3, 2])
[2, 1, 3] - 1 个逆序对 ([2, 1])
[2, 3, 1] - 2 个逆序对 ([2, 1], [3, 1])
[3, 1, 2] - 2 个逆序对 ([3, 1], [3, 2])
[3, 2, 1] - 3 个逆序对 ([3, 2], [3, 1], [2, 1])

在这些数组中，有两个数组恰好有 1 个逆序对。

[1, 3, 2]
[2, 1, 3]

因此，输出为 2。

Java 动态规划方法

import java. util.Scanner;
public class Solution {
   public static void main(String[] args) {
       Scanner scanner = new Scanner(System.in); 
       // Prompt the user to enter the value of n
System. out.print("Enter the value of n: ");
       int n = scanner.nextInt();
       // Prompt the user to enter the value of k
System. out.print("Enter the value of k: ");
       int k = scanner.nextInt();
       // Create an instance of the Solution class
       Solution solution = new Solution();
       // Call the kInversePairs method and print the result
       int result = solution.kInversePairs(n, k);
System.out.println("Number of arrays with exactly k inverse pairs: " + result); 
       // Close the scanner
scanner.close();
   }
   public int kInversePairs(int n, int k) {
       int[][] dp = new int[n + 1][k + 1];
       dp[0][0] = 1;
       int mod = 1000000007; 
       // Dynamic programming approach to calculate the number of arrays with exactly k inverse pairs
       for(int i = 1; i <= n; i++) {
           int val = 0;
           for(int j = 0; j <= k; j++) {
               val += dp[i - 1][j];
               if(j >= i) val -= dp[i - 1][j - i];
               if(val < 0) val += mod;
               val = (val % mod);
dp[i][j] = val;
           }
       }
       return (int)(dp[n][k]);
   }
}

输出

时间复杂度

kInversePairs 方法的渐进复杂度是 O(n*k)，即数组长度 'n' 与逆序对数量 'k' 的乘积。

空间复杂度

除了时间复杂度，它的空间复杂度也是 O(n*k)。原因是我们有一个大小为 (n + 1) * (k + 1) 的二维数组 'dp'。

使用动态规划的Java方法（不使用递归）

import java. util.Scanner;
public class Solution {
   public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in); 
       // Read inputs
System. out.print("Enter the value of n: ");
       int n = scanner.nextInt();
System. out.print("Enter the value of k: ");
       int k = scanner.nextInt();
       // Create an instance of Solution
       Solution solution = new Solution();
       // Call the kInversePairs method and print the result
System. out.println("Number of arrays with k inverse pairs: " + solution.kInversePairs(n, k)); 
       // Close the scanner
scanner.close();
   }
   public int kInversePairs(int n, int k) {
       // Define the modulo
       int modulo = 1_000_000_007; 
       // Check for invalid k
       if (inValidK(n, k)) {
           return 0;
       }
       // Initialize dp arrays
       int[] dp1 = new int[k + 1];
       int[] dp2 = new int[k + 1];
       dp1[0] = 1;
       dp2[0] = 1; 
       // Populate dp arrays
       for (int i = 2; i <= n; i++) {
           for (int j = 1; j <= k; j++) {
               dp2[j] = (dp2[j - 1] + dp1[j]) % modulo;
               if (j + 1 > i) {
dp2[j] = ((dp2[j] - dp1[j - i]) + modulo) % modulo;
               }
           }
           int[] temp = dp1;
           dp1 = dp2;
           dp2 = temp;
       }
       // Return result
       return dp1[k];
   }
   // Helper method to check for invalid k
   private boolean inValidK(int n, int k) {
       return (n * (n - 1)) / 2 < k;
   }
}

输出

时间复杂度

指数级时间复杂度为 O(n*k)，其中 n 是输入值，k 是输出值。这是因为在解法中存在 n 次迭代，每次迭代都需要对指定限制内的每个 'k' 值进行操作。

空间复杂度

该解法的空间复杂度为 O(k)，其中 'k' 是输入参数 'k' 的值。这是由于在应用动态规划方法时，使用了两个大小为 'k + 1' 的数组来存储中间结果。因此，空间大小随 'k' 值的增加而线性增长。

使用递归的Java方法

import java. util.Arrays;
import java. util.Scanner; 
class RecursiveMethod {
   int mod = 1_000_000_000 + 7;
   int[][] memo;
   // Recursive function to count the number of arrays with k inverse pairs
   public int count(int n, int k) {
       // Base cases
       if (n == 0) {
           return 0;
       }
       if (k == 0) {
           return 1;
       }
       if (memo[n][k] != -1) {
           return memo[n][k];
       }
       int res = 0;
       // Iterate through a possible number of inversions
       for (int inv = 0; inv <= Math.min(k, n - 1); inv++) {
           // Recursive call to count arrays with remaining inversions
           res = (res % mod + count(n - 1, k - inv) % mod) % mod; 
           // Each recursive call represents a subset of arrays with inversions
       }
       memo[n][k] = res;
       return res;
   }
   // Function to calculate the number of arrays with k inverse pairs
   public int kInversePairs(int n, int k) {
       memo = new int[n + 1][k + 1];
       // Initialize memoization array with -1
       for (int i = 0; i <= n; i++) {
Arrays.fill(memo[i], -1);
       }
       // Call recursive function to count arrays with k inverse pairs
       return count(n, k);
   }
   public static void main(String[] args) {
           Scanner scanner = new Scanner(System.in); 
       // Read inputs
System. out.print("Enter the value of n: ");
       int n = scanner.nextInt();
System. out.print("Enter the value of k: ");
       int k = scanner.nextInt();
       // Create an instance of Solution
       Solution solution = new Solution();
       // Call the kInversePairs method and print the result
System. out.println("Number of arrays with k inverse pairs: " + solution.kInversePairs(n, k)); 
       // Close the scanner
scanner.close();
   }
}

输出

时间复杂度

递归解法的时间复杂度是指数级的，因为对于 n 和 k 的每种组合，递归函数都会被调用很多次（不止一次）。它是 O(n * k)。

空间复杂度

同样，空间复杂度也是 O(n * k)，我们用一个记忆化数组来存储中间结果。该数组的大小为 n * k，其中 n=数组长度，k=形成的逆序对数量。

下一个主题节省内存的双向链表

K 反转对数组

问题陈述

示例 1

说明

示例 2

说明

Java 动态规划方法

时间复杂度

空间复杂度

使用动态规划的Java方法（不使用递归）

时间复杂度

空间复杂度

使用递归的Java方法

时间复杂度

空间复杂度

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

K 反转对数组

问题陈述

示例 1

说明

示例 2

说明

Java 动态规划方法

时间复杂度

空间复杂度

使用动态规划的Java方法（不使用递归）

时间复杂度

空间复杂度

使用递归的Java方法

时间复杂度

空间复杂度

相关帖子

展开链表

融合 vs 堆叠

将队列的前半部分与后半部分交错

N 元树的序列化和反序列化

使用 Map 进行二叉树的垂直顺序遍历

线段树 (带节点更新的范围最大查询)

二叉树枚举

区间树

BST 中给定键的中序前驱和后继

数据结构中栈的局限性

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器