在 O(nlogn) 中查找数组中的所有差异，其中 n 是元素的最大范围

Question

问题：给定一个已排序的数组 A，找出 A 中元素的所有可能差异，其中每个元素都是 [1, ..., n] 范围内的整数。此外，您可以假设没有重复项。所以数组的最大大小将 <= n。

注意：由于上述限制，可能的总差异将在 [1, ..., n-1] 的范围内。

示例（对于 N=12）：

输入：1、6、10、12
输出：2、4、5、6、9、11

问题与此类似，除了 n 是否。该问题中的元素数量，而不是元素的上限。

在同一个问题中也有一个答案，这个：https : //stackoverflow.com/a/8455336/2109808 这家伙声称它确实可以使用 fft 和自卷积在 O(nlogn) 中完成，但我不明白它，当我在在线卷积计算器上尝试它时，它似乎也不正确（就像这个）。

那么，有谁知道如何在 O(nlogn) 中实现这一点？

先感谢您 ：）

Answer 1

OP链接的这个答案建议采取以下步骤：

1. 假设一个数组在 [0, n -1].*范围内具有非重复元素
2. 创建一个长度为n的数组，其中索引与输入元素匹配的元素设置为 1，其他元素设置为 0。这可以在 O( n ) 中创建。例如，在输入数组中给出[1,4,5]，我们创建一个数组[0,1,0,0,1,1]。
3. 计算自相关函数。这可以通过采用 FFT、平方其幅度，然后采用 IFFT 来计算。这是 O( n log n )。
4. 对于对应于输入中存在的差异的索引，输出是非零的。索引 0 处的元素始终为非零，应被忽略。查找和打印这些元素是 O( n )。

请注意，此过程是不正确的，因为通过 FFT 计算的自相关函数是循环的。也就是说，给定具有两个值 0 和n -1的输入数组，输出将在索引 1 和索引n -1处具有非零元素。为避免这种情况，有必要在第 2 步中创建长度为 2 n的数组，将其一半设置为 0。然后应忽略输出数组的后半部分。将数组大小加倍不会改变算法的计算复杂度，仍然是 O( n log n )。

* 为简单起见，我更改了 OP 给出的范围，通过向所有索引添加偏移量来更改此范围是微不足道的。