比较两个长度相同的整数数组

(面试问题可能太复杂了。)

(您可以使用o(n)时间首先检查min、max、sum、sumsq等是否相等。)

使用 no-extra-space radix sort 对两个数组进行适当排序。o(n)时间复杂度,o(1)空间。

然后用常用算法进行比较。o(n)时间复杂度,o(1)空间。

(前提是(最大值-最小值)阵列为O(n ^钾 )以有限K。)

你可以尝试一种概率方法-把数组转换成一个大基数的数字 B 被一些质数修饰 P ,例如sum B^a_i 为了所有 i 修改一些大的 磷 . 如果它们都是同一个数,就可以再尝试任意多的素数。如果任何尝试都是错误的,那么它们是不正确的。如果他们通过了足够的挑战,那么他们是平等的, 高概率 .

有一个小小的证据 乙 gt; N , 磷 >最大数量。因此,一定有一个无法应对的挑战。这实际上是一种确定性的方法,尽管复杂性分析可能更困难,这取决于人们如何根据输入的大小来看待复杂性(而不仅仅是元素的数量)。

我主张:除非输入的范围是指定的,否则就不可能在恒定的额外空间和o(n)运行时间内求解。

我很乐意被证明是错的,这样我就能学到新的东西。

1. 将第一个数组中的所有元素插入哈希表
2. 尝试将第二个数组中的所有元素插入到同一哈希表中-因为每个insert to元素都应该已经存在

好吧,这不是恒定的额外空间,但我现在能想到的最好的:-)。对这个问题是否有其他限制,比如数组中可能包含的最大整数?

一些答案基本上是正确的,尽管它们看起来不像。哈希表方法(例如)具有基于 类型 而不是数组中元素的数量。至少根据大多数定义,这使得空间(上限)成为常数,尽管常数可能很大。

理论上,你可以把它从一个上限改为一个真正的常量空间。例如,如果您在C或C++中工作,它是一组 char ,您可以使用以下内容:

size_t counts[UCHAR_MAX];

由于uchar_max是一个常量,因此数组使用的空间量也是一个常量。

编辑:我注意到,在几乎 全部的 算法复杂性的描述。例如,我们都“知道”quicksort是一个o(n logn)算法。但是,如果我们假设比较和交换要排序的项需要恒定的时间,那么这是唯一正确的,只有在我们限定了范围的情况下,这才是正确的。如果所涉及的项目的范围足够大,我们不能再将比较或交换视为持续时间,那么它的复杂性将变成类似于o(n logn log r),如果r是范围,那么 log R 近似表示项所需的位数。

这是个骗人的问题吗?如果作者假设整数在给定的范围内(2^32等),那么“额外常量空间”可能只是一个2^32大小的数组,您可以在其中计算两个列表中的出现次数。

如果整数未被更改,则无法执行此操作。

可以将每个元素添加到hashmap<integer,integer>,规则如下:数组a是加法器,数组b是移除器。从数组A插入时,如果键不存在,请使用值1将其插入。如果密钥存在,则增加该值(保持计数)。移除时,如果密钥存在且大于1,则将其减少1。如果键存在且为1,则移除元素。

使用上面的规则遍历数组a和数组b。如果在移除阶段阵列b的任何时候未找到元素,则可以立即返回false。如果在加法器和移除器都完成之后,hashmap为空,那么数组是等价的。

编辑:哈希表的大小将等于数组中不同值的数目这是否符合常量空间的定义?

我认为这个解决方案需要某种转换,这种转换既有关联性又有交换性,并且保证了一组唯一输入的唯一结果。但我不确定这是否存在。

public static boolean match(int[] array1, int[] array2) {

        int x, y = 0;

        for(x = 0; x < array1.length; x++) {
                y = x;
                while(array1[x] != array2[y]) {
                        if (y + 1 == array1.length)
                                return false;
                        y++;
                }
                int swap = array2[x];
                array2[x] = array2[y];
                array2[y] = swap;
        }

        return true;
}

对于每个数组,使用计数排序技术生成小于或等于特定元素的元素数。然后在每个索引处比较两个构建的辅助数组,如果它们等于数组,则不等于。计数排序需要o(n),并且每个索引处的数组比较再次为o(n),因此它的o(n)和所需的空间总共等于两个数组的大小。下面是计数排序的链接 http://en.wikipedia.org/wiki/Counting_sort .

给定int在-n…+n范围内,检查公平性的简单方法如下(伪代码):

// a & b are the array
accumulator = 0
arraysize = size(a)
for(i=0 ; i < arraysize; ++i) {
  accumulator = accumulator + a[i] - b[i]
  if abs(accumulator) > ((arraysize - i) * n) { return FALSE }
}
return (accumulator == 0)

累加器必须能够存储范围为+-arraysize*n的整数

把两个数组中的所有数字都异或。如果结果为0,则匹配。