在数百万个数字中找到仅有的一个重复数字。

Question

这是我最近在Adobe的面试中遇到的一个难题：有一个包含数百万个未排序正整数的数组，其中所有元素都是唯一的，除了一个数字出现了两次。目标是以最优方式找到这个重复出现的数字。 P.S. 数组上绝对没有顺序/模式可供应用。 面试官拒绝了任何排序的可能性，因为那需要很长时间，他想让这个问题成为一个谜题，然后提出一个更聪明的解决方案。

- Vaibhav Arora

---

你觉得呢？ - laune

显然，“排序”数据并查找重复项是一种方法（或树结构或堆）。他们是否建议除O(n log n)之外的其他东西对于空间和时间来说是合理的？也许他们希望你问“在什么方面最优？” - Gordon Linoff

但是排序的时间复杂度是(n logn)，由于有数百万条记录，这将花费很长时间。他们需要一个聪明的方法来解决这个问题。 - Vaibhav Arora

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），这是以空间换时间的经典例子。

请记住，面试问题并不是为了弄清楚您是否有给定问题的解决方案，而是为了让面试官看到您的思维过程。往往情况下，您最大的优势不是算法的百科全书式知识，而是您智能地思考问题及如何解决它们的能力。

- paxdiablo

Answer 2

通过将值哈希到集合中，对数组进行单个顺序遍历即可找出重复项。这是O(n)的，但需要使用HashSet的内存和数据结构。哈希的最坏情况是在第一个和最后一个位置都有重复项。

即使排序25M个整数也很快，约为2秒，尽管它是O(n log n)，但具有相对恒定的时间，并且比哈希的最坏情况要快得多。另一方面，哈希可能会击败排序，以及下一种方法：

最快的方法是使用位图来注册数字（约1秒），尽管这可能需要大量内存（（0x7FFF_FFFF+1）/8-即非负整数的数量除以每字节的位数），但分配非常简单。同样，最坏的情况是在第一个和最后一个位置都有重复项。

以下是我用于比较的代码。像Java中的大多数朴素基准测试一样，应该谨慎使用。但它表明，任何方法的代码可读性都不是问题。

public class Duplicate {
    public static void main(String[] args) throws Exception {
        Random r = new Random( 100L );
        int[] a = new int[25000000];
        Set<Integer> set  = new HashSet<>(a.length/2);
        boolean dupl = true;
        for( int i = 0; i < a.length; ){
            int x = Math.abs( r.nextInt() );
            if( set.add( x ) ){
                a[i++] = x;
            }
        }
        a[a.length-1] = a[0]; // Worst case for HashSet and BitSet
        set = null;

        System.out.println( "hash " + new Date() );
        set  = new HashSet<>();
        for( int i = 0; i < a.length; ++i ){
            if( ! set.add( a[i] ) ){
                System.out.println( a[i] );
                break;
            }
        }
        set = null;

        System.out.println( "bitmap " + new Date() );
        BitSet bs = new BitSet( 0x7FFF_FFFF ); 
        for( int i = 0; i < a.length; ++i ){
            if( bs.get( a[i]-1 ) ){
                System.out.println( a[i] );
                break;
            }
            bs.set( a[i]-1 );
        }

        System.out.println( "sort "  + new Date());
        Arrays.sort( a );
        for( int i = 1; i < a.length; ++ i ){
            if( a[i] == a[i-1] ){
                System.out.println( a[i] );
                break;
            }
        }
        System.out.println( "done " + new Date() );
    }
}

注意，Java 8有Arrays.sortParallel。如果你有硬件支持，这将进一步减少排序时间。- 还要注意，位集方法是基于规范“正数”的。如果包括负数，将会使事情变得复杂，但我怀疑面试官想了解候选人对Java的java.util资源的“流畅性”。

- laune

---

@老程序员，我漏掉了一个“f”。抱歉。 - laune

由于此标记为Java，您可以使用(Integer.MAX_VALUE - Byte.SIZE) / Byte.SIZE + 1。 - greybeard

@老程序员 由于这不是程序代码，我会插入口头解释。感谢您的提示。 - laune

Answer 3

由于数据是无序的，你需要将每个数字与剩余的（n-1）个数字进行比较，因此时间复杂度为O(n^2)。他们要求一种时间复杂度小于O(n^2)的算法。为此，你需要使用树或哈希表。如果你对数据进行排序，然后再应用任何算法，那将是一个更耗时的过程。无论是树还是哈希表，你都需要O(n)的时间。因为它们都是最适合整理数据和查找数据的工具。

- Vikas.Ghode