那天看朋友提了一个百度面试的题目：怎么找出{1,1,2,3,3,4,4,4,5,5,5,5} 找出出现次数为奇数的数字.
我这里复制的是原话，当然顺序是不一定的，很多拿到题目第一反应就是用map,当然可以解决，但是效率不高。
还有人觉得应该用算法xxx,我是没想到用啥算法好...！
还有觉得应该先排序...
还有觉得用位图....bitmap 等等方法！
我都觉得麻烦，思维方式就是，从节省时间考虑，从数组来看，我们都得遍历一次数组里面的元素，那么我就想只遍历一次，就能得到结果的方法，然后由算法去优化，这是我通常考虑类似问题的办法。
第一种情况：
由于数组元素限定，我们先假设我们能知道最大的数字，我这里用另一组数据测试：
{1,1,2,3,5,3,6,8,7,2,3,8,3,4,4,4,5,5,5,5};
可以看出8 是最大的数字，那么我就可以建立一个长度为9的数组index[]，只要出现一次数字，就在相应的位置++。
比如数字1 ,那么我就在index[1] ++ .进行处理，那么循环一次之后我就知道每个元素出现的次数。
但是还得循环去判断是奇数还是偶数，这里做点小改进，在存放的时候就可以判断。比如，1 出现一次，我就在index[1] 的位置 设置为1，出现第二次，我就让index[1] 的位置变为0， 那么数组里面只要为1 的，都是出现的奇数，并且位置和元素等价，可以看代码。
static int[] nums = {1,1,2,3,5,3,6,8,0,7,2,3,8,3,4,4,4,5,5,5,5};
// 我假设我知道元素最大的数
static int maxNum = 9;
static int[] index = new int[maxNum];
public static void main(String[] args) {
// 计算个数
for(int i =0;i<nums.length;i++){
index[nums[i]] = ++index[nums[i]]/2 == 1?0:1;
}
// 打印
for(int i=0;i<index.length;i++){
if(index[i] == 1){
System.out.println("出现次数为奇数的数字有："+i);
}
}
}
OK，有人觉得不知道元素的最大数，这里有几种方案解决这种问题.
1.你可以直接建立一个大数组，Integer 的最大值的，当然里面必须是int 范围的。这样会浪费很多空间。
2.你可以给一个默认值，比如100，如果发现nums[i] 的值，大于数组长度了，那么就要进行扩容了， 值可以设大点，看你作何做出权衡。
小结：
1.这里仅仅提供一种思路，还不完善，可以进行修改，有更好的欢迎提供，非常感谢。
2.改进建议，能否节约空间，因为发现index 数组里面只需要为1 的，表示奇数的数，其他的浪费空间了。 还有算 ++ 操作 ，三目运算能否考虑算法，让执行能力更快，这些就交给有兴趣的朋友去啦，有东西了，希望分享哦~。~
———————————————————————————————————————————————
分 割 线
———————————————————————————————————————————————
看大家这么有兴趣，这里我综合了了一下意见：
第一种，按我的方法进行微量优化，不建立int,建立boolean ，节约空间
static int[] nums = {1,1,2,3,5,3,6,8,0,7,2,3,8,3,4,4,4,5,5,5,5,9,9,1024*1024*100};
// 我假设我知道元素最大的数 +1
static int maxNum = 1024*1024*100+1;
static boolean[] index = new boolean[maxNum];
public static void main(String[] args) {
// 计算个数
for(int i =0;i<nums.length;i++){
index[nums[i]] = index[nums[i]]^true == false?false:true;
}
// 打印
for(int i=0;i<index.length;i++){
if(index[i]){
System.out.println("出现次数为奇数的数字有："+i);
}
}
}
可以看出上面所占的字节数至少要1024*1024*100+1 也就是100M的空间，我们可以通过命令：
-Xmx64m -Xms64m 只允许64M，那么这里就OOM了
第二种，这里我采用5L的办法，做了一点改进，为了方便理解这个，我也做了详细的解释：
static int[] nums = {1,1,2,3,5,3,6,8,0,7,2,3,8,3,4,4,4,5,5,5,5,9,9,1024*1024*100*3};
// 我假设我知道元素最大的数
static int max = 1024*1024*100*3+1;
static byte[] bits = new byte[(max + 7) >> 3];
public static void main(String[] args) {
// 计算
for (int i = 0; i < nums.length; i++) {
set(nums[i]);
}
// 输出
for (int i = (bits.length << 3) - 1; i >= 0; i--) {
if (get(i)) {
System.out.println(i);
}
}
}
// 第一步，求出该数应该放在byte 数组哪个位置,相当于n/8 得出位置
// 比如1~7 之间的放[0] 相当于1~7/8 位置，8~15[1] 8~15/8位置，依次类推
public static int index(int n) {
return n >> 3;
}
// 第二步，计算n在数组里面的偏移量，比如：3%8 = 3,在数组里面的位置我们应该放在0000 0100 这种表示
public static int offset(int n) {
return n & 0x07;
}
// 第三步，刚才的位置和偏移量做异或运算，做异或的原因就是当出现偶数次的时候 进行归0
// 比如假设第一个数字 3，计算位置在[0] 的位置。默认 [0] 的bit 元素二进制：
// {0000 0000}
// 那么第一次就将1 << 3位，二进制是：0000 00001 << 3 == 0000 0100 ，然后将和[0] 位 // 置的做异或运算
// 0000 0000
// ^0000 0100
// 0000 0100 这表示已经存放了一次值：3
// 如果第二个元素还是3,再次操作就变成了：0000 0000,就归0了
public static void set(int n) {
bits[index(n)] ^= (1 << offset(n));
}
// 获取位置的元素，从最高位开始遍历，假设bit数组两个长度分别是：
// [0]=>{0000 1000} 3
// [1]=>{0010 0100} 13 10
// 总长度也就是16位，当我们获取get[15] 的时候，
// 以同样的方式可以得到15/8 = 7的位置在[1] 里面的最高位,也就是0
// 如果是get[3],那么获取的就是[0],4/8 = 4 位置的1,这里位置通过位移操作完成的
public static boolean get(int i) {
return (bits[index(i)] & 1 << offset(i)) != 0;
}
可以看出，我们允许的范围增加了很多，理论上可以增加8倍。
关于内存限制这块，可以通过命令：
Runtime r = Runtime.getRuntime(); System.out.println(r.totalMemory()/1024/1014); System.out.println(r.maxMemory()/1024/1014); System.out.println(r.freeMemory()/1024/1014); 大概估计，但是我们并不能建立一个byte[r.maxMemory()] 我JDK1.7 的限制在r.maxMemory()*0.69 就 OOM了，我记得可以通过命令调节，但是- -忘记命令了。
小结：
1.很高兴大家有兴趣来研究这种小算法，更加熟悉嘛。
2.关于评论的算法，我尝试了，有数组越界，得不到正确结果等，需要改进，可以尝试增大数据进行
3.算法同样是不完善的，还有改进的余地，多专研啦~。~ 还有一些边界问题，考虑不周。
4.关于bit 类似的计算，可以专门花时间看看，可以尝试大文件的的一些处理哦
5。有不正确的地方还请指正。
相关推荐
企业公司软件测试面试笔试题集合 软件测试面试题 （测试基础）.doc 01_企业面试试卷（综合）.doc 01_企业面试试卷（综合）_参考答案.doc 04_企业面试试卷（测试基础）.doc 04_企业面试试卷（测试基础）_参考答案.doc...
可以这么说，绝大部分的面试题，都是这100 道题系列的翻版， 此微软等公司数据结构+算法面试100 题系列，是极具代表性的经典面试题。 而，对你更重要的是，我自个还提供了答案下载，提供思路，呵。 所以，这份资料+...
中兴面试题 1>某人在某个市场某个商家买了某台电脑,请用你熟悉的计算机语言表达出里面的关系. 其中有商家类，买家类，商品类。还要有买方法，卖方法。 2>一个完整的单例模式 3>曹操南下攻打刘备，刘备派关羽守...
我们会一直不断地更新和充实该宝典，同时也希望读者朋友能够多多提供优质的面试题，也许下一个版本就有你提供的面试题哦。该宝典系统地整理了Java初级,中级,高级的基础知识,代码质量,解题思路,优化效率等面试要点,...
刚刚做完百度的笔试题，真心觉得不难，但由于时间不够所以没能全部写完，表示遗憾，笔试的最后一道我已经忘了原题，大概的意思是先将一个矩阵转置成另一个矩阵，然后两个矩阵相乘，最后返回二维数组，其实很简单。
第一部分为一道百度面试题 Top K 算法的详解；第二部分为关于 Hash 表算法的详细阐述；第三部分为打造一个最快的 Hash 表算法。
一篇hash算法的介绍 第一部分为一道百度面试题 Top K 算法的详解 ； 第二部分为关于 Hash 表算法的详细阐 述；第三部分为打造一个最快的 Hash 表算法。
最近面试遇到了一道面试题，顿时有点迷糊，只说出了思路，后来百度了一下，整理了一下思路，于是记录下来，方便以后学习。（面试题请参见附件） 相关的数据表： 1.Score表 2.[User]表 SQL语句如下： –方法一：静态...
本资源精心收录了多家知名企业（包括奇安信、贝壳找房、小米、游卡、vivo、阿里巴巴、爱奇艺、百度、猿辅导、中兴等）的C++方向笔试题，覆盖从2020年至2022年的秋招和校招题目。这些题目不仅考察了C++的基础知识，如...
第一篇 面试题 ................................................................................ 8 1.1. 简介 ................................................................................................
一道著名外企面试题的抽丝剥茧 ......................................................................74 C/C++结构体的一个高级特性――指定成员的位数 .........................................................
但最近我在换工作的时候遇到一道合并数组的面试题，我当时想的是将两个数组先转化为字符串，合并后再转化为数组输出，面试官说这个思路不太对，完了bulabula讲了一下数组基础的东西，然后确实是因为经验问题，或者是...
今天我们进入《Java常用基础知识》专题，动力节点Java资源库整合了近年各大厂的面试中的常见问题和知识点。每天更新10个，我们的最终目标就是大厂，若对题目有疑问，可在公众号后台留言提问。 目标：阿里巴巴、腾讯...
本文实例讲述了C++实现将一个...这是道很好的题目，也是百度面试中的一道题，题目不难，但是问题得考虑全面。这里给出如下实现代码： #include #include #include using namespace std; int findNumberFirst(const