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也会比较节省空间.
相关推荐
c++面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试...
java面试题! java面试题! java面试题! java面试题! java面试题! java面试题!
百度面试题大收集百度面试题大收集百度面试题大收集
百度 移动 面试题百度 移动 面试题百度 移动 面试题百度 移动 面试题百度 移动 面试题百度 移动 面试题百度 移动 面试题百度 移动 面试题百度 移动 面试题百度 移动 面试题
齐全的面试题,当前主流互联网公司 百度 腾讯 等面试题库 相当实用的文档,百度面试通过全靠它了
百度笔试面试题,挺全的,百度面试还没到,细心准备吧。
面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题...
百度 Android 开发面试题 1、 Android dvm 的进程和 Linux 的进程, 应用程序的进程是否为同一个概念 DVM 指 dalivk 的虚拟机。每一个 Android 应用程序都在它自己的进程中运行, 都拥有一个独立的 Dalvik 虚拟机...
VUE面试题三.zipVUE面试题三.zipVUE面试题三.zipVUE面试题三.zipVUE面试题三.zipVUE面试题三.zipVUE面试题三.zipVUE面试题三.zipVUE面试题三.zipVUE面试题三.zipVUE面试题三.zipVUE面试题三.zipVUE面试题三.zipVUE...
去百度面试的时候 百度内部人士给的面试题资料 很有用
百度面试题第三题及答案.doc;百度面试题第三题及答案.doc;百度面试题第三题及答案.doc
百度android开发面试题,android面试试题
网盘下载pdf文件,包括常见前端面试题汇总,百度、阿里、腾讯校招面试题汇总,网盘下载pdf文件,65个文件
【BAT必备】分布式相关面试题大全面试题【BAT必备】分布式相关面试题大全面试题【BAT必备】分布式相关面试题大全面试题【BAT必备】分布式相关面试题大全面试题【BAT必备】分布式相关面试题大全面试题【BAT必备】...
百度普遍的面试题库,但不局限于所提供的题目。可以参考下。
百度面试题
2010年百度面试题 2011年毕业的同学有用
百度2013年移动开发岗位面试题(南京)
JAVA面试题JAVA面试题JAVA面试题JAVA面试题JAVA面试题JAVA面试题
阿里面试20题 百度面试10题 华为面试10题 京东面试13题 腾讯面试37题 头条面试10题 项目经理面试常遇问题 经典面试题 程序员 IT经理 项目经理 面试题 研发经理 高级程序员 经典面试题