我正在编写一个算法，该算法将返回一个具有确定长度和反转次数（数字对，其中左侧数字大于右侧数字）的数组。即数组 [3, 1, 4, 2] 包含三个反演 (3, 1), (3, 2) 和 (4, 2)。所以在实践中，当给定长度 n=3 和反转次数 k=3 时，算法应该生成一个数组 [3, 1, 4, 2] （或另一个满足这些要求的数组）。
由于反转次数也是按升序对数组进行排序所必须进行的交换次数，因此我通过创建一个从 1 到 n - 1 的数组并反向使用插入排序算法来解决这个问题k 交换。
这种方法适用于较小的输入，但该算法应该能够有效地生成高达 n=10^6 和 k=n(n-1)/2 以及介于两者之间的任何数组，因此该算法应该在 O (n log n) 时间而不是 O(n^2)。下面是代码：
import java.util.*;
public class Inversions {
public int[] generate(int n, long k) {
// Don't mind these special cases
if (n == 1) {
int[] arr = {1};
return arr;
}
if (k == 0) {
int[] arr = …