区分多个元素和两个数组？

Question

我的一位朋友在接受采访时被问到这个问题 -

• 您已经给出了两个大小为10的整数数组.
• 两者都包含9个相等的元素(比如说1到9)
• 只有一个元素是不同的.

你怎么会找到不同的元素？您可以采取哪些不同的方法？

一个简单但冗长的方法是 - 对两个数组进行排序,继续比较每个元素,在进行错误比较时,您将获得结果.

那么有什么不同的方法呢？在面试中指定逻辑.不期望特定语言的特定代码.伪代码就足够了.

(每个答案请提交一种方法)

我提出这个问题的目的是,当数组大小很小时就可以了.但是当数组大小增加时,你必须考虑一种非常有效的方法.在这种情况下,使用比较绝不可取.

Answer 1

如果你需要这个扩展,那么我将使用世界上许多Set实现之一.例如,Java的HashSet.

抛出Set中的所有第一个数组.然后,对于第二个数组的每个成员,如果它包含在Set中,则将其删除; 否则将其标记为Unique#2.在此过程之后,Set的最后一个剩余成员是Unique#1.

我可能会这样做,即使是在采访中,甚至是简单的十元素阵列.生活太短暂,无法花时间找到一个聪明的方法来缩放墙壁,当它有一个非常好的门.

Answer 2

这是一种数学方法,受凯文的​​答案及其评论的启发.

让我们分别调用数组A并B让它们的唯一元素为a和b.首先,取两个数组的总和,然后减去另一个; 因为其他一切都取消了,sum(A) - sum(B) = a - b = s.然后,将两个数组的元素相乘,然后将它们相互分开.事情再次取消,所以mult(A) / mult(B) = a / b = r.现在,从这些,我们得到a = rb,rb - b = s或b = s / (r - 1)如此a = rs / (r - 1).

我称之为数学,因为在实际程序中将事物放在一起可能不合理.关键是要有两个不同的操作,它们既可以单独允许取消行为,又可以分配到另一个上面.这个后一个属性是从rb - b = sto到的时候使用的b = s / (r - 1),比如说,使用加法和XOR,这是我的第一次尝试.

Answer 3

这可以从两个序列的平方和和之间快速求解.并且计算这些总和肯定会比建议的哈希更快,并且不涉及序列项之间的任何比较.

这是怎么做的:如果两个集合是{ a _i }和{ b _i },那么将A和B称为它们的和,A2和B2是平方的总和,即A2 = Sum({ a _i ² }} ),为方便起见,D = AB,D2 = A2-B2.因此,D = ab和D2 = a ² -b ²,其中a和b是两个不同的元素,从中我们看到

a =(D ² + D2)/(2*D)
b = a -D

这工作,因为,从代数,一个² -b ² =(A + B)(AB)或D2 =(A + B)d,使A + B = D2/d,并且由于我们也知道AB,我们可以找到a和b.

Python中的一个例子可能更有说服力

a, b = 5, 22   # the initial unmatched terms
x, y = range(15), range(15)
y[a] = b
print "x =", x  # x = [0, 1, 2, 3, 4,  5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
print "y =", y  # y = [0, 1, 2, 3, 4, 22, 6, 7, 8, 9, 10, 11, 12, 13, 14]

D = sum(x) - sum(y)
D2 = sum([i**2 for i in x]) - sum([i**2 for i in y])  #element-wise squaring
a = (D2+D*D)/(2*D)
b = a - D

print "a=%i, b=%i" % (a, b)
#prints a=5, b=22  which is correct

(当然,这有点类似于jk的答案,除了它不需要所有项的乘法和可能产生的巨大数字,但是由于jk的数学方法的想法.)