在 O(n log n) 时间内生成具有 n 个长度和 k 个反转的数组的算法？

Question

我正在编写一个算法，该算法将返回一个具有确定长度和反转次数（数字对，其中左侧数字大于右侧数字）的数组。即数组 [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 = 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 time) 中工作，但无济于事。

如果你们有一些想法，那就太好了。如果您不熟悉 Java，没关系，非常欢迎伪代码或任何其他类型的建议！

Answer 1

如果反转数组中的初始m 个元素，则会创建m(m-1)/2 个反转。

如果反转初始的m+1 个元素，则会创建m(m+1)/2 个反转。

它们之间的区别仅是m。

所以：

1. 生成排序数组
2. 找到最大的m，使得m(m-1)/2 <= k
3. 反转数组中的前m 个元素以创建m(m-1)/2 个反转
4. 将下一个元素向前移动k - m(m-1)/2 个位置以创建剩余的所需反转。

这需要O(n)时间，这比您需要的要好。