百度一道面试题的三种解法

http://greemranqq.iteye.com/blog/2069056 

在上面的地址看到了一个百度面试的题目：怎么找出{1,1,2,3,3,4,4,4,5,5,5,5}  找出出现次数为奇数的数字.

 

 

个人总结了一下,在上面博文加评论里面共提到了2种方法.

1)使用一个数组来记录出现的次数,数组下标为对应的数,数组的值为出现的次数

2)使用BitMap来实现,这样可以用非常小的内存记录非常大的值域范围,只需要1位就可以记录一个Int. 并且用这一位的值,就可以反应出奇偶次数

 

 

我想到了另外一种方法(方法3), 使用集合Set来存储出现次数为奇数的数.直接过滤次数为偶数的数.

import java.util.HashSet;
import java.util.Set;

public class Interview {
	public static Integer[] input = { 1, 1, 2, 3, 3, 4, 4, 4, 5, 5, 5, 5 };

	public static void main(String[] args) {
		//用来存储最终奇数结果
		Set<Integer> resultSet = new HashSet<Integer>();
		
		for (Integer element : input) {
			if (resultSet.contains(element)) {
				//如果已经出现(说明是偶数),就删除
				resultSet.remove(element);
			} else {
				//如果没有找到,说明是奇数次
				resultSet.add(element);
			}
		}
		//遍历,打印结果
		for (Integer element : resultSet) {
			System.out.println(element);
		}

	}
}

 

这个方法解决了下面的问题(只提优点,缺点就不说了^__^)

1)对比方案一,不需要预先初始化一个大数组.特别是输入List重复度比较高的时候,就会节省空间.

2)在打印最后结果时,上面2种方法都需要重新遍历一个小的集合才能得到次数为奇数的数字.集合的大小,取决于输入的List的里面的最大值和最小值的差值.

3)上面2种方法,都一定程度上为出现偶数次的数准备了空间,存在一定的浪费.如果使用Set只存储出现奇数次的数,如果恰好每个数出现的顺序相对集中时会比较节省空间.如果这个List比较稀疏,方案3也会比较节省空间.