我正在编写一个算法，它将返回一个确定长度和逆转数（左侧数字大于右侧数字的数字对数）的数组。例如，数组 [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)。以下是代码：
算法返回的数组与样本结果不完全相同，但通过了所有测试，除了输入规模非常大的测试。我尝试了不同的变体使用归并排序，因为它可以在O(n log n时间)内工作，但未能解决问题。
如果您有任何想法，那将是太棒了。如果您不熟悉Java，也没关系，伪代码或任何其他类型的建议都可以！
这种方法可以很好地处理较小的输入，但该算法应能够有效地生成长达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 = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = 1;
}
return arr;
}
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = i + 1;
}
int inversions = 0;
int i = 0;
while (inversions < k && i < n) {
int j = i - 1;
while (j >= 0 && arr[j] < arr[j + 1] && inversions < k) {
int helper = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = helper;
inversions++;
j--;
}
i++;
}
return arr;
}
}
用于测试不同输入数组的主要类：
public class Main {
public static void main(String[] args) {
Inversions in = new Inversions();
int[] arr1 = in.generate(4,3);
int[] arr2 = in.generate(4,0);
int[] arr3 = in.generate(4,6);
System.out.println(Arrays.toString(arr1)); // [3,1,4,2]
System.out.println(Arrays.toString(arr2)); // [1,1,1,1]
System.out.println(Arrays.toString(arr3)); // [4,3,2,1]
}
}
算法返回的数组与样本结果不完全相同，但通过了所有测试，除了输入规模非常大的测试。我尝试了不同的变体使用归并排序，因为它可以在O(n log n时间)内工作，但未能解决问题。
如果您有任何想法，那将是太棒了。如果您不熟悉Java，也没关系，伪代码或任何其他类型的建议都可以！