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

[Description] Given two integer arrays with the same length. Design an algorithm which can judge whether they're the same. The definition of "same" is that, if these two arrays were in sorted order, the elements in corresponding position should be the same.

给定两个长度相同的整数数组。设计一种能够判断它们是否相同的算法。“same”的定义是，如果这两个数组按排序顺序排列，那么相应位置的元素应该是相同的。

[Example]
<1 2 3 4>  = <3 1 2 4>
<1 2 3 4> != <3 4 1 1>

[Limitation] The algorithm should require constant extra space, and O(n) running time.

[限制]算法需要恒定的额外空间和O(n)运行时间。

12 个解决方案

#1

(Probably too complex for an interview question.)

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

(You can use O(N) time to check the min, max, sum, sumsq, etc. are equal first.)

(你可以用O(N)时间检查最小、最大值、总和、sumsq等是否相等。)

Use no-extra-space radix sort to sort the two arrays in-place. O(N) time complexity, O(1) space.

使用无额外空间的基数排序对两个数组进行排序。O(N)时间复杂度，O(1)空间。

Then compare them using the usual algorithm. O(N) time complexity, O(1) space.

然后用通常的算法进行比较。O(N)时间复杂度，O(1)空间。

(Provided (max − min) of the arrays is of O(N^k) with a finite k.)

(提供(最大−最小)的数组是O(Nk)和一个有限的k。)

#2

You can try a probabilistic approach - convert the arrays into a number in some huge base B and mod by some prime P, for example sum B^a_i for all i mod some big-ish P. If they both come out to the same number, try again for as many primes as you want. If it's false at any attempts, then they are not correct. If they pass enough challenges, then they are equal, with high probability.

你可以尝试一个概率方法——把数组转换成一个数字在某些巨大的基地一些' P,B和国防部例如总和我^ ai所有国防部big-ish P .如果他们都出来相同数量,再试一次,你想要尽可能多的质数。如果任何尝试都是错误的，那么它们就不正确。如果他们通过了足够多的挑战，那么他们是平等的，有很高的可能性。

There's a trivial proof for B > N, P > biggest number. So there must be a challenge that cannot be met. This is actually the deterministic approach, though the complexity analysis might be more difficult, depending on how people view the complexity in terms of the size of the input (as opposed to just the number of elements).

对于B > N P >最大的数有一个平凡的证明。因此，一定存在着无法应对的挑战。这实际上是确定性的方法，尽管复杂性分析可能更加困难，这取决于人们如何从输入的大小(而不是元素的数量)来看待复杂性。

#3

I claim that: Unless the range of input is specified, then it is IMPOSSIBLE to solve in onstant extra space, and O(n) running time.

我断言:除非输入的范围被指定，否则不可能在连续的额外空间和O(n)运行时间中解决。

I will be happy to be proven wrong, so that I can learn something new.

我会很高兴被证明是错的，这样我就能学到新的东西。

#4

Insert all elements from the first array into a hashtable
将第一个数组中的所有元素插入哈希表
Try to insert all elements from the second array into the same hashtable - for each insert to element should already be there
尝试将第二个数组中的所有元素插入到同一个hashtable中——对于每个元素的插入都应该已经存在

Ok, this is not with constant extra space, but the best I could come up at the moment:-). Are there any other constraints imposed on the question, like for example to biggest integer that may be included in the array?

好吧，这不是用恒定的额外空间，而是我目前能想到的最好的:-)。是否对这个问题施加了其他约束，例如对数组中可能包含的最大整数的约束?

#5

A few answers are basically correct, even though they don't look like it. The hash table approach (for one example) has an upper limit based on the range of the type involved rather than the number of elements in the arrays. At least by by most definitions, that makes the (upper limit on) the space a constant, although the constant may be quite large.

一些答案基本上是正确的，尽管看起来不像。哈希表方法(例如)基于所涉及类型的范围而不是数组中元素的数量有一个上限。至少在大多数定义中，这使得(上限)空间为常数，尽管常数可能相当大。

In theory, you could change that from an upper limit to a true constant amount of space. Just for example, if you were working in C or C++, and it was an array of char, you could use something like:

理论上，你可以把它从一个上限变成一个真正的常数空间。举个例子，如果你在C或c++工作，它是一个char数组，你可以使用如下内容:

size_t counts[UCHAR_MAX];

Since UCHAR_MAX is a constant, the amount of space used by the array is also a constant.

因为UCHAR_MAX是一个常量，所以数组所使用的空间也是一个常量。

Edit: I'd note for the record that a bound on the ranges/sizes of items involved is implicit in nearly all descriptions of algorithmic complexity. Just for example, we all "know" that Quicksort is an O(N log N) algorithm. That's only true, however, if we assume that comparing and swapping the items being sorted takes constant time, which can only be true if we bound the range. If the range of items involved is large enough that we can no longer treat a comparison or a swap as taking constant time, then its complexity would become something like O(N log N log R), were R is the range, so log R approximates the number of bits necessary to represent an item.

编辑:我要说明的是，在几乎所有的算法复杂性的描述中，都隐含着对所涉及项目范围/大小的限制。例如，我们都“知道”快速排序是一个O(N log N)算法。但是，如果我们假设对排序项进行比较和交换需要常数时间，这是正确的，这只有在我们限定范围的情况下才能成立。如果项目涉及的范围足够大,我们可以不再治疗比较或交换为常数时间,那么它的复杂性将成为类似O(N O(log N)日志R),R是范围,所以日志R接近所需的比特数来表示一个项目。

#6

Is this a trick question? If the authors assumed integers to be within a given range (2^32 etc.) then "extra constant space" might simply be an array of size 2^32 in which you count the occurrences in both lists.

这是个脑筋急转弯吗?如果作者认为整数在一定范围内(2 ^ 32等等),那么“额外的恒定的空间”可能只是一个数组的大小2 ^ 32数出现在两个列表。

If the integers are unranged, it cannot be done.

如果整数是未排列的，则无法完成。

#7

You could add each element into a hashmap<Integer, Integer>, with the following rules: Array A is the adder, array B is the remover. When inserting from Array A, if the key does not exist, insert it with a value of 1. If the key exists, increment the value (keep a count). When removing, if the key exists and is greater than 1, reduce it by 1. If the key exists and is 1, remove the element.

您可以将每个元素添加到hashmap 中，使用以下规则:数组a是adder，数组B是remover。当从数组A插入时，如果键不存在，则插入一个值为1的键。如果键存在，则增加值(保持计数)。当删除时，如果键存在且大于1，则将其减少1。如果键存在且为1，则删除元素。

Run through array A followed by array B using the rules above. If at any time during the removal phase array B does not find an element, you can immediately return false. If after both the adder and remover are finished the hashmap is empty, the arrays are equivalent.

使用上面的规则遍历数组A后面跟着数组B。如果在移除相位阵列B的任何时候没有找到一个元素，您可以立即返回false。如果在adder和remover完成之后hashmap是空的，那么数组是等价的。

Edit: The size of the hashtable will be equal to the number of distinct values in the array does this fit the definition of constant space?

编辑:hashtable的大小将等于数组中不同值的数量，这符合常量空间的定义吗?

#8

I imagine the solution will require some sort of transformation that is both associative and commutative and guarantees a unique result for a unique set of inputs. However I'm not sure if that even exists.

我想这个解需要某种变换它同时具有结合性和可交换性并且保证了唯一输入的唯一结果。但是我不确定这是否存在。

#9

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;
}

#10

-1

For each array, Use Counting sort technique to build the count of number of elements less than or equal to a particular element . Then compare the two built auxillary arrays at every index, if they r equal arrays r equal else they r not . COunting sort requires O(n) and array comparison at every index is again O(n) so totally its O(n) and the space required is equal to the size of two arrays . Here is a link to counting sort http://en.wikipedia.org/wiki/Counting_sort.

对于每个数组，使用计数排序技术来构建小于或等于一个特定元素的元素个数。然后比较两个在每一个指标上建立的辅助阵列，如果它们r相等，r相等，而不是。计数排序需要O(n)并且每个索引上的数组比较都是O(n)所以总的来说它的O(n)和所需的空间等于两个数组的大小。这里有一个指向计数排序的链接http://en.wikipedia.org/wiki/Counting_sort。

#11

-1

given int are in the range -n..+n a simple way to check for equity may be the following (pseudo code):

给定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)

accumulator must be able to store integer with range = +- arraysize * n

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

#12

-1

How 'bout this - XOR all the numbers in both the arrays. If the result is 0, you got a match.

这个怎么样——x或者两个数组中的所有数字。如果结果是0，就得到匹配。

#1