在 O(nlogn) 中查找数组中的所有差异，其中 n 是元素的最大范围
Find all differences in an array in O(nlogn) where n is the max range of elements
问题：给定一个排序数组 A，找出与 A 的元素的所有可能差异，其中每个元素都是 [1, ..., n] 范围内的整数。此外，您可以假设没有重复项。所以数组的最大大小将是 <= n.
注意：由于上述限制，可能的总差异将在 [1, ..., n-1] 范围内。
示例（对于 N=12）：
Input: 1, 6, 10, 12
Output: 2, 4, 5, 6, 9, 11
问题与this one类似，只是n是编号。该问题中元素的数量，而不是元素的上限。
同样的问题还有一个答案，这个：
这个人声称它真的可以使用 fft 和自卷积在 O(nlogn) 中完成，但我不明白，而且当我在在线卷积计算器上尝试时它似乎也不正确（比如 this one） .
那么，有人知道如何在 O(nlogn) 中实现吗？
提前谢谢你:)
This answer 由 OP 链接建议执行以下步骤：
- 假设数组 non-repeating 个元素在范围 [0, n-1].*
- 创建一个长度为n的数组，其中索引与输入的一个元素匹配的元素设置为1，其他元素设置为0。这可以在O中创建(n)。例如，给定输入数组
[1,4,5]，我们创建一个数组 [0,1,0,0,1,1].
- 计算自相关函数。这可以通过采用 FFT、对其量值求平方，然后采用 IFFT 来计算。这是 O(n log n).
- 对于与输入中存在的差异对应的索引，输出为 non-zero。索引 0 处的元素始终为 non-zero，应将其忽略。查找和打印这些元素是 O(n).
请注意，这个过程是不正确的，因为通过 FFT 计算的 auto-correlation 函数是循环的。也就是说，给定一个具有两个值 0 和 n-1 的输入数组，输出将在索引 1 和索引 [=19= 处有一个 non-zero 元素]n-1。为避免这种情况，有必要在步骤 #2 中生成长度为 2n 的数组，将其中一半设置为 0。然后应忽略输出数组的后半部分.将数组大小加倍不会改变算法的计算复杂度，它仍然是 O(n log n).
* 为了简单起见，我更改了 OP 给出的范围，通过向所有索引添加偏移量来更改此范围是微不足道的。
问题：给定一个排序数组 A，找出与 A 的元素的所有可能差异，其中每个元素都是 [1, ..., n] 范围内的整数。此外，您可以假设没有重复项。所以数组的最大大小将是 <= n.
注意：由于上述限制，可能的总差异将在 [1, ..., n-1] 范围内。
示例（对于 N=12）：
Input: 1, 6, 10, 12
Output: 2, 4, 5, 6, 9, 11
问题与this one类似，只是n是编号。该问题中元素的数量，而不是元素的上限。
同样的问题还有一个答案，这个： 这个人声称它真的可以使用 fft 和自卷积在 O(nlogn) 中完成，但我不明白，而且当我在在线卷积计算器上尝试时它似乎也不正确（比如 this one） .
那么，有人知道如何在 O(nlogn) 中实现吗？
提前谢谢你:)
This answer 由 OP 链接建议执行以下步骤：
- 假设数组 non-repeating 个元素在范围 [0, n-1].*
- 创建一个长度为n的数组，其中索引与输入的一个元素匹配的元素设置为1，其他元素设置为0。这可以在O中创建(n)。例如，给定输入数组
[1,4,5]，我们创建一个数组[0,1,0,0,1,1]. - 计算自相关函数。这可以通过采用 FFT、对其量值求平方，然后采用 IFFT 来计算。这是 O(n log n).
- 对于与输入中存在的差异对应的索引，输出为 non-zero。索引 0 处的元素始终为 non-zero，应将其忽略。查找和打印这些元素是 O(n).
请注意，这个过程是不正确的，因为通过 FFT 计算的 auto-correlation 函数是循环的。也就是说，给定一个具有两个值 0 和 n-1 的输入数组，输出将在索引 1 和索引 [=19= 处有一个 non-zero 元素]n-1。为避免这种情况，有必要在步骤 #2 中生成长度为 2n 的数组，将其中一半设置为 0。然后应忽略输出数组的后半部分.将数组大小加倍不会改变算法的计算复杂度，它仍然是 O(n log n).
* 为了简单起见，我更改了 OP 给出的范围，通过向所有索引添加偏移量来更改此范围是微不足道的。