java - 在百万个数字中只找到一个重复数字

Question

最近在 adobe 采访中有人问我这个难题:-有一个包含数百万个无序正数的数组，其中所有元素都是不同的，除了一个恰好出现两次的数字。动机是以最佳方式找到两次出现的数字。

附言绝对没有订单/模式适用于阵列。

面试官拒绝任何形式的可能性，因为那会花费很多时间，他想把问题当作一个谜题，然后提出一个更聪明的解决方案。

Answer 1

第一种方法是对数组进行排序，然后遍历排序后的数据，直到找到两个相同的连续数字。这可以在 O(n log n) 时间和 O(1) 空间内轻松完成。

如果面试官随后询问是否有更好的方法，您将讨论数据可能存在的任何限制(顺序/模式并不必然暗示对数据没有任何限制).您还应该质疑它们实际上意味着最佳 - 如果没有测量数量，该术语本身意义不大。

有些人优化时间，有些人优化空间，有些人(比如我)甚至优化代码可读性:-)

在讨论限制方面，一个例子是如果数字的范围被限制在几百万。然后创建一个计数数组并在 O(n) 时间内处理所有数据将是一件简单的事情，例如:

dim array[several million] as zero
for each number:
    array[number]++
    if array[number] == 2:
        print number
        stop

即使没有这样的限制，一个 32 位的数字范围也可以使用大约 40 亿位的数组(大约 500M)，这就是用空间换取时间的经典示例。 p>

请记住，面试问题并不是要弄清楚您是否有针对给定问题的解决方案，而是让面试官可以看到您的思维过程。通常，您最大的 Assets 不是算法的百科全书式知识，而是您智能地思考问题以及如何解决问题的能力。