在 O(n log n) 时间内生成长度为 n 且反转次数为 k 的数组的算法？

Question

我正在编写一个算法，该算法将 return 一个具有确定长度和反转次数的数组（数字对，其中左侧数字大于右侧数字）。 IE。数组 [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;
    }
}

以及用于测试不同输入数组的主要 class：

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]
    }
}

该算法没有return与示例结果完全相同的数组，但通过了所有测试，除了输入大小非常大的那些。我还尝试了合并排序的不同变体，因为它在 O(n log n time) 中工作但无济于事。

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

Answer 1

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

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

这两者的区别只有m.

所以：

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

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

Answer 2

另一个O(n)算法：从排序数组开始。当您交换第一个和最后一个元素时，您会得到 x = 2 * (n-2) + 1 个反转。考虑这两个元素是固定的，只处理剩余的数组。如果 x 太大，请考虑使用较小的数组。根据需要重复此操作。

未经测试的代码：

for (int first=0, last = n-1; remainingInversions>0; ) {
    int x = 2 * (last-first-1) + 1;
    if (x <= remainingInversion) {
        first++;
        last--;
        remainingInversion -= x;
    } else {
        last--; // consider a smaller array
    }
}

Answer 3

事实上，每次将最后一个元素与其前面的元素交换时，反转次数都会增加。这是一个 java 解决方案：

public static int[] generate(int n, long k) {
    int[] arr = new int[n];

    for(int i = 0; i < n; i++) {
        arr[i] = i;
    }

    long inversions = 0;
    int j = (n-1);
    int s = 0;

    while(inversions < k) {
        int temp = arr[j];
        arr[j] = arr[j-1];
        arr[j-1] = temp;

        inversions++;
        j--;
        if(j == s) {
            j = (n-1);
            s++;
        }
    }

    return arr;
}

Answer 4

我在 Python 中得到了一个具有 O(n) 复杂度的实现。

它基于两个规则。

反转大小为 m 的数组会得到 m*(m-1)/2 个反转。
将元素移动 m 个位置，创建 m 个反转。

def get_m(k):
    m=0
    while m*(m-1)/2<=k:
        m+=1
    else:
        m-=1
    return m

def generate(l, k):
    """
    Generate array of length l with k inversions.
    """
    # Generate a sorted array of length l
    arr = list(range(0,l))
    
    # If no inversions are needed, return sorted array. 
    if k==0:
        return arr
    
    # Find largest m such that m*(m-1)/2 <= k
    m=get_m(k)

    # Reverse first m elements in the array which will give m*(m-1)/2 inversions
    arr = arr[m-1::-1]+arr[m:]

    # Calculate for any remaining inversions
    remaining_k = k-(m*(m-1)/2)

    # For remaining inversions, move the last element to its left by remaining_k
    if remaining_k>0:
        arr.insert(int(len(arr)-remaining_k - 1), arr[-1])
        arr = arr[:-1]
    return arr

if __name__ == '__main__':
    l = int(sys.argv[1])
    k = int(sys.argv[2])
    arr = generate(l, k)
    print(arr)

Answer 5

@zhong yang：它在预期范围内工作得很好 0 <= k <= n(n-1)/2 但最好抛出异常或 null 如果 k 不在这个范围而不是返回一些数组！

Answer 6

有一种非常简单的方法可以创建 n 个反转... 也就是将最后一个元素移到最前面。由于使用了额外的内存，它不是很有效，但我会这样做：

创建一个长度为n 两倍的数组。如果我们使用 Integer[] 而不是 int[]，则用标记（即 null）从开始到中间填充它。从中间填充它，上升。然后做类似下面的事情...... 我确信我有一个错误和其他错误，但一般的想法在下面的代码中得到了体现。

int start = 0;
int mid = arr.length / 2;
int end = arr.length - 1;

while (v > 0)
{
    if (v < (end - mid))
    {
        arr[start++] = arr[mid + v];
        arr[mid + v] = null;
    }
    else
    {
        arr[start++] = arr[end];
        v -= (end - mid);
        end--;
    }
}

所以我们有一个数组，其中填充了起始值、一堆空值，然后是原始增量值，其中一个可能已变为空值，以及一个指向原始区域中间的“结束”指针.

所以最后一步是从 0 -> endPos 复制到最终数组，忽略空值。

Answer 7

如果k >= n - 1，则将元素n - 1 放在数组的最前面，使其与n - 1 个元素倒置；否则将其放在数组的最后，使其与 0 个元素倒置。继续这种贪婪方法来确定其余元素的去向。

这是一个解决方案，它通过一些数学知识在线性时间内将 generate() 实现为运行。

public class Inversions {

  public static int[] generate(int n, long k) {

    int[] array = new int[n];
    
    // locate k in various sums of (n-1), (n-2), ..., 1
    int a = (int) Math.sqrt((n * (n - 1) - 2 * k)); // between the sum of [(n-1)+...+(n-a)] and the sum of [(n-1)+...+(n-a-1)]
    int b = n - 1 - a; // counts of (n-1), (n-2), ..., (n-a)
    int c = (int) (k - n * b + (b * b + b) / 2); // spillover = k - [(n-1)+(n-b)]*b/2;

    // put elements in the array
    for (int i = 0; i < b; i++) {
        array[i] = n - 1 - i;
    }
    for (int i = b; i < n - 1 - c; i++) {
        array[i] = i - b;
    }
    array[n - 1 - c] = n - 1 - b;
    for (int i = n - c; i < n; i++) {
        array[i] = i - b - 1;
    }

    return array;

  }

  public static void main(String[] args) {

    int n = Integer.parseInt(args[0]);
    long k = Long.parseLong(args[1]);

    for (int i = 0; i < n; i++) {
        StdOut.print(generate(n, k)[i] + " ");
    }

  }
}

Answer 8

逻辑并不难。例如，我们有 10 个数字 [0,1,2,3,4,5,6,7,8,9] 来生成 18 个反转。首先，在0之前插入9，--->[9,0,1,2,3,4,5,6,7,8]，产生9次反转。还剩下 9 个反转，所以我们在 0 之前插入 8，---->[9,8,0,1,2,3,4,5,6,7]，所以我们得到额外的 8 个反转。最后还剩1个倒置，我们在6----->[9,8,0,1,2,3,4,5,7,6]前插入7个。在这种情况下我只使用数组。该程序以 O(n) 复杂度运行。下面的代码只考虑n个数(0,1,2.....n-1)及其倒数。

    public static int[] generate(int n, long k) {
    int[] a = new int[n];
    int[] b = new int[n];
    for (int i = 1; i < n; i++) {
        a[i] = 1 + a[i - 1];
    }
    if (n == 0 || k == 0) return a;
    else {
        int i = 0;
        while (k > 0) {
            if (k > n - i - 1) {
                b[i] = a[n - 1 - i];
            }
            else {
                //auxilary array c to store value 
                int[] c = new int[(int) (k + 1)];
                for (int j = i; j < n - 1 - k; j++) {
                    b[j] = j - i;
                }
                for (int j = (int) (n - 1 - k); j < n; j++) {
                    c[j - (int) (n - 1 - k)] = j - i;
                }
                b[(int) (n - 1 - k)] = c[(int) k];
                for (int j = (int) (n - k); j < n; j++) {
                    b[j] = c[j - (int) (n - k)];
                }
                break;
            }
            k = k - (n - 1 - i);
            i++;

        }
        return b;
    }
}

在 O(n log n) 时间内生成长度为 n 且反转次数为 k 的数组的算法？

Algorithm to generate an array with n length and k number of inversions in O(n log n) time?

java

algorithm

performance

sorting

inversion