在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.

Question: Given a sorted array A find all possible difference of elements from A, where each element is an integer in the range [1, ..., n]. Also, you can assume there are no duplicates. So max size of the array will be <= n.

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

Note: Total possible differences will be in the range of [1, ..., n-1] because of the above constraints.

示例(对于N = 12):

Example (for N=12):

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

Input: 1, 6, 10, 12
Output: 2, 4, 5, 6, 9, 11

该问题类似于这一个， n是编号.问题中元素的数量，而不是元素的上限.

The question is similar to this one, except n is the no. of elements in that question, not the upper bound of the element.

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

There's also an answer in the same question, this one: https://stackoverflow.com/a/8455336/2109808 This guy claims it can really be done in O(nlogn) using fft and self convolution, but I don't get it, and it also seems to be incorrect when I try it on online convolution calculators (like this one).

那么，有人知道如何在O(nlogn)中实现这一目标吗?

So, does anyone know how this can be achieved in O(nlogn)?

预先感谢您:)

推荐答案

由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 ).

1. Assume an array with non-repeating elements in the range [0, n-1].*
2. Create an array of length n, where elements whose index matches an element of the input are set to 1, other elements are set to 0. This can be created in O(n). For example, given in input array [1,4,5], we create an array [0,1,0,0,1,1].
3. Compute the autocorrelation function. This can be computed by taking the FFT, squaring its magnitude, and then taking the IFFT. This is O(n log n).
4. The output is non-zero for indices corresponding to a difference present in the input. The element at index 0 is always non-zero, and should be ignored. Finding and printing these elements is O(n).

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

Note that this process is not correct, because the auto-correlation function as computed through the FFT is circular. That is, given an input array with two values, 0 and n-1, the output will have a non-zero element at index 1 as well as at index n-1. To avoid this, it would be necessary to make the array in step #2 of length 2n, leaving half of it set to 0. The second half of the output array should then be ignored. Doubling the array size doesn't change the computational complexity of the algorithm, which is still O(n log n).

*为了简单起见，我更改了OP给出的范围，通过向所有索引添加偏移量来更改此范围很简单.

* I changed the range from that given by OP for simplicity, it is trivial to change this range by adding an offset to all indices.

这篇关于在O(nlogn)中查找数组中的所有差异，其中n是元素的最大范围的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！