问题描述
一个int的数组,有些数字只出现一次，有些数字出现两次，只有一个数字出现了3次，求出现3次的这个数字，不可以用额外的空间（用位操作）
解决方案
解决方案二：
不用额外的空间你怎么遍历这个数组？
解决方案三：
引用1楼vnvlyp的回复:
不用额外的空间你怎么遍历这个数组？
4点多还不睡觉啊，注意休息啊。
解决方案四：
先把数据排序，交换值时用下面的位操作。inta=2;intb=3;a^=b;b^=a;a^=b;
排好序之后就很容易找出3个相同的了
解决方案五：
引用3楼zmcmm的回复:
先把数据排序，交换值时用下面的位操作。inta=2;intb=3;a^=b;b^=a;a^=b;排好序之后就很容易找出3个相同的了
关键你能不用额外空间进行排序吗？循环变量都没有的排序还真是不会。
解决方案六：
没有限制复杂度，直接先排序，再比较即可。两个关键点：1.排序的时候，两个位置的交换，通过a[i]=a[i]+a[j];a[j]=a[i]-a[j];a[i]=a[i]-a[j];或者用LZ说的异或操作也行2.比较的时候从下标1比较到a.length-2遍历，a[i]与a[i-1]、a[i+1]比较，就可以得到3个重复的了
解决方案七：
引用5楼oh_Maxy的回复:
没有限制复杂度，直接先排序，再比较即可。两个关键点：1.排序的时候，两个位置的交换，通过a[i]=a[i]+a[j];a[j]=a[i]-a[j];a[i]=a[i]-a[j];或者用LZ说的异或操作也行2.比较的时候从下标1比较到a.length-2遍历，a[i]与a[i-1]、a[i+1]比较，就可以得到3个重复的了
解决方案八：
这个看似是可以的，不知道是不是面试官的想法。引用5楼oh_Maxy的回复:
没有限制复杂度，直接先排序，再比较即可。两个关键点：1.排序的时候，两个位置的交换，通过a[i]=a[i]+a[j];a[j]=a[i]-a[j];a[i]=a[i]-a[j];或者用LZ说的异或操作也行2.比较的时候从下标1比较到a.length-2遍历，a[i]与a[i-1]、a[i+1]比较，就可以得到3个重复的了
解决方案九：
这种算法题真是头疼，是不是还有更好的算法呢？？？求高手
解决方案十：
是这个意思不？？packagecom.gao.csdn;importjava.util.ArrayList;importjava.util.Collection;importjava.util.HashSet;importjava.util.Iterator;importjava.util.Set;/***一个int的数组,有些数字只出现一次，*有些数字出现两次，只有一个数字出现了3次，*求出现3次的这个数字，不可以用额外的空间（用位操作*@authorpcgmy**/publicclassArrayHelp{/***@paramargs*/publicstaticvoidmain(String[]args){//TODOAuto-generatedmethodstubintarr[]=newint[]{1,1,3,5,5,6,7,5};//set为不重复的集合Set<Integer>cot=newHashSet<Integer>();//遍历数组for(inti=0;i<arr.length;i++){cot.add(arr[i]);}Iterator<Integer>it=cot.iterator();//增强for循环while(it.hasNext()){intk=0;inti=it.next();for(intj=0;j<arr.length;j++){if(arr[j]==i){k++;}}if(k==3){System.out.println(i);}}}}
解决方案十一：
回答楼上，这题主要是要求用位操作去做，但是没有要求复杂度，所以有点没思路了，你的方法也许可行但是不符合要求啊（位操作）
解决方案十二：
这面试题，难道真的无解了，我在网上也搜到过，但是光有题目，没有答案。哎！
解决方案十三：
引用9楼sg19911227的回复:
是这个意思不？？packagecom.gao.csdn;importjava.util.ArrayList;importjava.util.Collection;importjava.util.HashSet;importjava.util.Iterator;importjava.util.Set;/***一个int的数组,有些数字只出现一次，*有些数字出现两次，只有一个数字出现了3次，*求出现3次的这个数字，不可以用额外的空间（用位操作*@authorpcgmy**/publicclassArrayHelp{/***@paramargs*/publicstaticvoidmain(String[]args){//TODOAuto-generatedmethodstubintarr[]=newint[]{1,1,3,5,5,6,7,5};//set为不重复的集合Set<Integer>cot=newHashSet<Integer>();//遍历数组for(inti=0;i<arr.length;i++){cot.add(arr[i]);}Iterator<Integer>it=cot.iterator();//增强for循环while(it.hasNext()){intk=0;inti=it.next();for(intj=0;j<arr.length;j++){if(arr[j]==i){k++;}}if(k==3){System.out.println(i);}}}}
不行的，集合框架本身就申请了额外空间了；另外，凡是面试题，尽量少用集合框架，不然等着被对手PK掉。
解决方案十四：
引用12楼SmallYamateh的回复:
Quote: 引用9楼sg19911227的回复:
是这个意思不？？packagecom.gao.csdn;importjava.util.ArrayList;importjava.util.Collection;importjava.util.HashSet;importjava.util.Iterator;importjava.util.Set;/***一个int的数组,有些数字只出现一次，*有些数字出现两次，只有一个数字出现了3次，*求出现3次的这个数字，不可以用额外的空间（用位操作*@authorpcgmy**/publicclassArrayHelp{/***@paramargs*/publicstaticvoidmain(String[]args){//TODOAuto-generatedmethodstubintarr[]=newint[]{1,1,3,5,5,6,7,5};//set为不重复的集合Set<Integer>cot=newHashSet<Integer>();//遍历数组for(inti=0;i<arr.length;i++){cot.add(arr[i]);}Iterator<Integer>it=cot.iterator();//增强for循环while(it.hasNext()){intk=0;inti=it.next();for(intj=0;j<arr.length;j++){if(arr[j]==i){k++;}}if(k==3){System.out.println(i);}}}}不行的，集合框架本身就申请了额外空间了；另外，凡是面试题，尽量少用集合框架，不然等着被对手PK掉。
看到这个，你就想起有人连char数组逆序都不考虑中文2个char的问题，竟然还能20k的月薪。真是各花入各眼。会不会被pk掉真的难说
解决方案十五：
期待正确答案。。。。..
解决方案：
想想排序：冒泡，插入此类的，每个数都需要与其他数一一比较，那么，单独拿出每个数去和其他比较，异或2次为0！？够低下的效率吧。但是，快排之类的与之前类算法还用到了数值本身大小，但这道题只比较数值，我暂时就想到这些。~！
解决方案：
publicstaticvoidmain(String[]args){int[]array=newint[]{1,5,3,6,8,5,1,45,54,54,54,3,212,105,106,105,105};for(inti=0;i<array.length;i++){if(i!=0){for(intn=i;n>0;n--){if(array[n]<array[n-1]){inta=array[n];array[n]=array[n-1];array[n-1]=a;}else{break;}}}}for(inti=0;i<array.length;i++){if(i<array.length-2){if(array[i]==array[i+1]&&array[i]==array[i+2]){System.out.println(array[i]);break;}}}}
不晓得对不对
解决方案：
publicstaticvoidmain(String[]args){intnum=100;int[]array=newint[num];//添加数据for(inti=0;i<array.length-2;i++){intcount=0;for(intj=i+1;j<array.length;j++){if((array[i]^array[j])==0){count++;}}if(count==2){System.out.println(array[i]);}}}具体的验证没有做！
解决方案：
如果真的是面试题的话,答不出来,可以写自己知道的方法,总比空着好varnums=[1,2,3,5,3,2,8,77,54,33,2,4,6,12,13,5,88,33,22];varnumMap={};for(variinnums){varnum=nums[i];if(nums[i]==3){alert(num);break;}if(!numMap[num]){numMap[num]=1;}else{numMap[num]++;}}
解决方案：
引用18楼thc1987的回复:
如果真的是面试题的话,答不出来,可以写自己知道的方法,总比空着好varnums=[1,2,3,5,3,2,8,77,54,33,2,4,6,12,13,5,88,33,22];varnumMap={};for(variinnums){varnum=nums[i];if(nums[i]==3){alert(num);break;}if(!numMap[num]){numMap[num]=1;}else{numMap[num]++;}}
改下varnums=[1,2,3,5,3,2,8,77,54,33,2,4,6,12,13,5,88,33,22];varnumMap={};for(variinnums){varnum=nums[i];if(nums[num]==3){alert(num);break;}if(!numMap[num]){numMap[num]=1;}else{numMap[num]++;}}
解决方案：
1,排序2,找值packagetest;publicclassFindTarget{privatestaticinttemp;publicstaticvoidmain(String[]args){inttarget[]={3,5,2,2,7,8,9,6,1,1,0,6,6};//sortfor(inti=0;i<target.length;i++){for(intj=i+1;j<target.length;j++){if(target[i]>target[j]){temp=target[i];target[i]=target[j];target[j]=temp;}}}//3timeshasappearedfor(inti=0;i<target.length-2;i++){if(target[i]==target[i+1]){if(target[i]==target[i+2]){System.out.print(target[i]+"");}}}}}
解决方案：
publicclassFind3Times{publicstaticvoidmain(String[]args){int[]array={1,2,3,4,3,5,6,2,3,0,1};for(inti=0;i<array.length-1;i++){for(intj=array.length-1;j>i;j--){if(array[j]<array[j-1]){array[j]^=array[j-1];array[j-1]^=array[j];array[j]^=array[j-1];}}}for(inti=0;i<array.length-2;i++){if(array[i]==array[i+1]&&array[i]==array[i+2]){System.out.println(array[i]);}}}}
解决方案：
publicclassTestJava{staticint[]array=newint[21];intflag=0;publicvoidaddElement(){for(inti=0;i<6;i++){for(intj=0;j<=i;j++){array[flag++]=i+1;}}}publicstaticvoidmain(String[]args){intflag=0;TestJavatestJava=newTestJava();testJava.addElement();for(intm=0;m<array.length;m++){for(intn=0;n<array.length;n++){if((array[m]^array[n])==0){flag++;if(flag==6){System.out.println(array[m]);return;}};}flag=0;}}}
解决方案：
publicclassSuozu{publicstaticvoidmain(String[]args){int[]arr={1,2,1,3,4,5,6,7,5,6,8,9,10,1,12};for(inti=0;i<arr.length-2;i++){for(intj=i+1;j<arr.length-1;j++){for(intk=j+1;k<arr.length;k++){if(arr[i]==arr[j]&&arr[i]==arr[k]){System.out.println("arr["+i+"]=arr["+j+"]=arr["+k+"]="+arr[i]);break;}}}}}}
缸入门的菜鸟，没学过位运算，用学到的基础for做了一个，沾边吗？
解决方案：
publicstaticvoidmain(String[]args)throwsIOException{int[]arr={1,2,2,3,3,5,5,6,6,6,7,7};intrs=arr[0];for(inti=0;i<arr.length;i++){rs^=~arr[i];System.out.println(rs);}System.out.println(rs);}
解决方案：
有个小BUG修正一下int[]arr={1,1,1,2,2,3,3,5,5,6,6,7,7};intrs=arr[0];for(inti=1;i<arr.length;i++){rs^=~arr[i];}System.out.println(rs);
解决方案：
但是有出现一次的啊，25楼的方法就不行了吧
解决方案：
引用26楼buptcjj的回复:
但是有出现一次的啊，25楼的方法就不行了吧
没问题，可以拿来试试的
解决方案：
不用额外空间不能遍历数组还真没想出来。期待正确答案。
解决方案：
位操作好像leetcode上边看到过一道题，貌似用的是亦或运算来找到不同的值，如果这道题没有出现一次的数字的话，从头到位亦或一次就行。不过这道题貌似不行，想不出来。。。
解决方案：
inton(int[]some){for(inti=some.length-1;i>=2;){intthe=some[i];intcount=0;for(intj=--i;j>=0;j---){if(some[j]==the&&(++count==2)){returnthe;}}}return0;}
解决方案：
不可以用额外的空间（用位操作）不知道这样行不行（for循环里面的i，j算是额外的空间吗……）另外算法复杂度要不要考虑……publicstaticvoidmain(String[]args){inta[]={8,3,10,10,5,3,3,5,6};for(inti=0;i<a.length;i++){for(intj=i+1;j<a.length;j++){if(a[i]>a[j]){a[i]=a[i]^a[j];a[j]=a[i]^a[j];a[i]=a[i]^a[j];}}}for(inti=0;i<a.length-2;i++){if(a[i]==a[i+1]&&a[i+1]==a[i+2]){System.out.print(a[i]);}}}
解决方案：
publicclassSearchTest{publicstaticvoidmain(String[]args){int[]a={10,2,3,4,5,6,7,8,9,3,2,4,6,7,8,10,10,2};for(inti=0;i<a.length;i++){for(intj=i+1;j<a.length;j++){if(((a[i]&a[j])==a[j])&&((a[i]&a[j])==a[i])){//System.out.println("i的数为:"+i+"j的数为:"+j);for(intk=j+1;k<a.length;k++){//System.out.println("j的数为:"+j+"k的数为:"+k);if((a[j]&a[k])==a[k]&&(a[j]&a[k])==a[j]){System.out.println("找到的数为:"+a[k]);continue;}}}}}}}不知道这样行不行，就测试了几个数，
解决方案：
publicclassFindNum{publicstaticvoidmain(String[]args){int[]a={1,2,2,3,3,3,..};if((a[0]&a[1])==a[0]){if((a[0]&a[2])==a[0]){System.out.println("您要找的是："+a[0]);}elseif..{}elseif((a[0]&a[a.length-1])==a[0]){System.out.println("您要找的是："+a[0]);}}elseif((a[0]&a[2])==a[0]){..}elseif..{}elseif((a[0]&a[a.length-2)==a[0]){..}if((a[1]&a[2])==a[1]){..}elseif..{}if..{}if((a[a.length-3]&a[a.length-2])==a[a.length-3]){..}}}
解决方案：
上面12行括号写错了，应为..&a[a,length-2])==..
解决方案：
这个是完整的代码吗？能大概讲下思路吗？引用33楼Std_Wang的回复:
publicclassFindNum{publicstaticvoidmain(String[]args){int[]a={1,2,2,3,3,3,..};if((a[0]&a[1])==a[0]){if((a[0]&a[2])==a[0]){System.out.println("您要找的是："+a[0]);}elseif..{}elseif((a[0]&a[a.length-1])==a[0]){System.out.println("您要找的是："+a[0]);}}elseif((a[0]&a[2])==a[0]){..}elseif..{}elseif((a[0]&a[a.length-2)==a[0]){..}if((a[1]&a[2])==a[1]){..}elseif..{}if..{}if((a[a.length-3]&a[a.length-2])==a[a.length-3]){..}}}
解决方案：
思路就是不定义任何中间变量，循环控制变量，自然就不会申请额外的空间，利用A&A=A的关系，从a[0]开始利用if分支语句逐一查找，每当找到有3个相同元素，输出该元素
解决方案：
当然上面那段代码不是完整的，我只是试着将我的想法写出来而已
解决方案：
看到代码有点跪了，居然可以这么做
解决方案：
#include<stdio.h>#include<stdlib.h>intmain(){intarrays[11]={1,2,3,2,5,6,3,4,3,2};inti=0,j=0,k=0;for(i=0;i<10;i++)for(j=i+1;j<10;j++)for(k=j+1;k<10;k++){if(((arrays[i]|~arrays[j])==~0)&&((arrays[i]&~arrays[j])==0))if(((arrays[i]|~arrays[k])==~0)&&((arrays[i]&~arrays[k])==0))printf("a[%d]=%d,a[%d]=%d,a[%d]=%dn",i,arrays[i],j,arrays[j],k,arrays[k]);}system("pause");return1;}
解决方案：
39楼正解，。。。
解决方案：
引用39楼gojoy_x13的回复:
#include<stdio.h>#include<stdlib.h>intmain(){intarrays[11]={1,2,3,2,5,6,3,4,3,2};inti=0,j=0,k=0;for(i=0;i<10;i++)for(j=i+1;j<10;j++)for(k=j+1;k<10;k++){if(((arrays[i]|~arrays[j])==~0)&&((arrays[i]&~arrays[j])==0))if(((arrays[i]|~arrays[k])==~0)&&((arrays[i]&~arrays[k])==0))printf("a[%d]=%d,a[%d]=%d,a[%d]=%dn",i,arrays[i],j,arrays[j],k,arrays[k]);}system("pause");return1;}
C语言有点忘了,有人能翻译成java语言不
解决方案：
有点扯，遍历数组也得有个下标变量吧，这都不准用么
解决方案：
好像只要这样就可以得到那个三次出现的数了。int[]arr={1,1,2,2,3,3,3,5,5,6,6,7,7,8};intcount=0;for(inti=0;i<arr.length;i++){count=0;//每次count都要清0for(intj=i;j<arr.length;j++){if((~arr[i]&arr[j])==0)//两个数相同{count++;}if(count==3)//碰到两次相同的数，说明此数有三个，找到该数{System.out.println("这就是你要找的数..."+arr[j]);break;}}}
解决方案：
反正就是不能用int我是这样理解的那就用3循环publicstaticvoidmain(String[]args){int[]arr={1,1,2,2,3,3,3,5,5,6,6,7,7,8};for(inti=0;i<arr.length-2;i++){for(intj=i+1;j<arr.length-1;j++){if(arr[i]==arr[j]){for(intk=j+1;k<arr.length;k++){if(arr[j]==arr[k]){System.out.println("出现三次的数为"+arr[k]);break;}}}else{continue;}}}}
解决方案：
参考异或的思路写的，谢过3楼publicintfind(int[]arr){Arrays.sort(arr);for(inti=0;i<arr.length-2;i++){if(((arr[i+1]^arr[i])==0)&&((arr[i+1]^arr[i+2])==0)){returnarr[i];}}return0;}
解决方案：
引用41楼hcb1208的回复:
Quote: 引用39楼gojoy_x13的回复:
#include<stdio.h>#include<stdlib.h>intmain(){intarrays[11]={1,2,3,2,5,6,3,4,3,2};inti=0,j=0,k=0;for(i=0;i<10;i++)for(j=i+1;j<10;j++)for(k=j+1;k<10;k++){if(((arrays[i]|~arrays[j])==~0)&&((arrays[i]&~arrays[j])==0))if(((arrays[i]|~arrays[k])==~0)&&((arrays[i]&~arrays[k])==0))printf("a[%d]=%d,a[%d]=%d,a[%d]=%dn",i,arrays[i],j,arrays[j],k,arrays[k]);}system("pause");return1;}C语言有点忘了,有人能翻译成java语言不
感觉像是考:xor(^)xor可以表示=，因为不能用中间变量存储，所以就使用xor了