检查数组B是否是A的排列

Question

我试图找到一个解决方案,但无法摆脱我的困扰.

我们给出了两个未排序的整数数组A和B.我们必须检查数组B是否是A的排列.如何做到这一点.甚至对数字进行异或也不会有效,因为可能存在几个具有相同XOR值bt的反例并不是彼此的排列.

解决方案需要O(n)时间和空间O(1)

欢迎任何帮助!! 谢谢.

Answer 1

问题是理论上的,但你可以在O(n)时间和o(1)空间中进行.分配一个包含2 ^32个计数器的数组,并将它们全部设置为零.这是O(1)步骤,因为数组具有恒定的大小.然后遍历两个数组.对于数组A,递增与读取的整数对应的计数器.对于数组B,递减它们.如果在数组B的迭代期间遇到负计数器值,则停止---数组不是彼此的排列.否则在最后(假设A和B具有相同的大小,先决条件)计数器数组全部为零,并且两个数组是彼此的排列.

这是O(1)空间和O(n)时间解决方案.然而,这是不切实际的,但很容易通过作为面试问题的解决方案.至少它应该.

更加模糊的解决方案

• 使用非确定性计算模型,检查两个数组不是彼此的排列可以在O(1)空间中完成,O(n)时间通过猜测在两个数组上具有不同计数的元素,然后计数两个数组上该元素的实例.

• 在随机化计算模型中,构造随机交换哈希函数并计算两个数组的哈希值.如果散列值不同,则阵列不是彼此的排列.否则他们可能会.重复多次以使误差概率低于所需阈值.也在O(1)空间O(n)时间方法,但随机化.

• 在并行计算模型中,让'n'为输入数组的大小.分配'n'个线程.每个线程i = 1 .. n从第一个数组中读取第i个数; 让那是x.然后,同一个线程计算第一个数组中x的出现次数,然后检查第二个数组上的相同计数.每个线程使用O(1)空间和O(n)时间.

• 将整数数组[a1,...,an]解释为多项式x ^a1 + x ^a2 + ... + x ^an其中x是自由变量,并且数值检查所获得的两个多项式的等价性.使用浮点算术进行O(1)空间和O(n)时间操作.由于舍入误差并且因为等价的数值检查是概率性的,因此不是精确的方法.或者,将多项式解释为以素数为模的整数,并执行相同的概率检查.

Answer 2

如果允许我们自由访问大量素数列表,您可以通过利用素数因子分解的属性来解决这个问题.

对于两个数组,计算每个整数i的Prime [i]的乘积,其中Prime [i]是第i个素数.如果它们是彼此的排列,则阵列的乘积的值是相等的.

推理因子化有两个原因.

1. 乘法是可传递的,因此计算产品的操作数的顺序是无关紧要的.(有人提到这样一个事实,即如果对数组进行排序,这个问题将是微不足道的.通过乘法,我们隐式排序.)
2. 素数无损地增加.如果我们得到一个数字,并告诉它只是素数的乘积,我们可以准确计算出哪些素数被输入到它中以及究竟有多少素数.

例:

a = 1,1,3,4
b = 4,1,3,1
Product of ith primes in a = 2 * 2 * 5 * 7 = 140
Product of ith primes in b = 7 * 2 * 5 * 2 = 140

也就是说,我们可能不允许访问素数列表,但这似乎是一个很好的解决方案,所以我想我会发布它.

Answer 3

我为发布这个作为答案而道歉,因为它应该是对antti.huima答案的评论,但我还没有声誉可以发表评论.

计数器数组的大小似乎是O(log(n)),因为它取决于输入数组中给定值的实例数.

例如,让输入数组A全为1,长度为(2 ^ 32)+ 1.这将需要一个33位大小的计数器进行编码(实际上,这将使数组的大小加倍,但让我们坚持理论).A的大小加倍(仍为1个值),每个计数器需要65位,依此类推.

这是一个非常挑剔的论点,但这些面试问题往往非常挑剔.