这是我最近在Adobe的面试中遇到的一个难题:有一个包含数百万个未排序正整数的数组,其中所有元素都是唯一的,除了一个数字出现了两次。目标是以最优方式找到这个重复出现的数字。
P.S. 数组上绝对没有顺序/模式可供应用。
面试官拒绝了任何排序的可能性,因为那需要很长时间,他想让这个问题成为一个谜题,然后提出一个更聪明的解决方案。
dim array[several million] as zero
for each number:
array[number]++
if array[number] == 2:
print number
stop
即使没有这样的限制,32位数字范围也可以使用大约40亿个位的数组(约500M),这是以空间换时间的经典例子。
请记住,面试问题并不是为了弄清楚您是否有给定问题的解决方案,而是为了让面试官看到您的思维过程。往往情况下,您最大的优势不是算法的百科全书式知识,而是您智能地思考问题及如何解决它们的能力。
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资源的“流畅性”。
(Integer.MAX_VALUE - Byte.SIZE) / Byte.SIZE + 1
。 - greybeard