数组中只出现一次的数字

1.题目:
给定一个数组,数组中只有2个数字出现了一次,其余都出现了2次,找出这2个数字。
2.思路:
方法一:哈希法:暴力解法,直接存储每个数出现的次数,与《数组中出现次数超过一半的数字》的解法类似
时间复杂度:O(n)
空间复杂度:O(n)
//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果

import java.util.HashMap;
public class Solution {
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        HashMap<Integer,Integer> hashMap=new HashMap<>();
        for(int i=0;i<array.length;i++){
            if(hashMap.containsKey(array[i])){
                hashMap.put(array[i],hashMap.get(array[i])+1);
            }else{
                hashMap.put(array[i],1);//仅出现一次的
            }
        }
        int count=0;//计数,分别赋予
        for(int j=0;j<array.length;j++){
            if(hashMap.get(array[j])==1){
                if(count==0){
                    num1[0]=array[j];
                ++count;
                }else{
                    num2[0]=array[j];
                }
            }
        }
    }
}

方法二:位运算、异或法(理解了好久)
前提知识:
异或运算:如果a、b两个值不相同,则异或结果为1。如果a、b两个值相同,异或结果为0。一个数异或两遍不同的数还是为这个数,如a^b^b=a;

n^0 = n;
n^n = 0;
n^n^m = n^(n^m) 满***换律 
n^m^m=n

所以,我们可以让数组中的每一个数异或一下,最后会得到一个结果ret,就是两个出现一次的数字的异或结果这个结果肯定是由两个不同数字异或而来,因此我们找ret二进制中为1的位置i,因为1一定是由0,1异或而来,因此要求得两个数中,一定有一个数的二进制中的第i个位置为1, 一个为0.
如何找到位置i?可用i = ret & (-ret),因为计算机用补码存取二进制数,而负数的补码为反码+1,举个例子
假如ret = 1110 , -ret = 0010 , 所以 i = 0010所以,再异或一遍即可得到答案。
//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果

public class Solution {
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        int temp = array[0];
        for(int i=1;i<array.length;i++){
            temp=temp^array[i];//每个数异或一遍因为a^b^b=a,则最终结果为两个只出现一次的数的异或
            //,稍后找到出现1的那一位来区分,在这里,我们取出现1的第一位
        }
         int index=1;//分类变量
            while((index&temp)==0){
                index=index<<1;//左移×2,找到temp的二进制中第一位1的位置i,找到后跳出循环
            }//这里也可以用temp=&(-temp)直接找到
            int res1=0;
            int res2=0;
            for(int j=0;j<array.length;j++){//遍历整个数组后分为两类
                if((index&array[j])==0){//第一类,在i处有1的数
                    res1=res1^array[j];//此处也就用到了a^b^b=a,直接找出那个数
                }else{//第二类,在i处无1的数
                    res2=res2^array[j];
                }
            }
            num1[0]=res1;
            num2[0]=res2;
    }
}

方法三:利用ArrayList来解决
这个可以使用ArrayList来解决,代码比较简洁。
首先判断ArrayList中是否已存在,如果存在,则删除。
删除时需要注意一下,如果直接传入当前数作为参数,它会按照下标进行删除,不会按照对象进行删除,可能会出现越界。
所以需要new Integer()。

import java.util.ArrayList;
public class Solution {
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        ArrayList<Integer> list = new ArrayList();
        for(int i=0;i<array.length;i++){
            if(list.contains(array[i])){
                list.remove(new Integer(array[i]));
            }else{
                list.add(array[i]);
            }
        }
          num1[0] = list.get(0);
          num2[0] = list.get(1);
    }
}
全部评论

相关推荐

1.&nbsp;事件概述3月10日下午,华为在“心声社区”发布长达6500字通报,曝光72名正式员工及19名非雇员在非雇员招聘中存在徇私舞弊行为,多人出卖公司信息资产获利,引发热议。-&nbsp;“非雇员”一般指华为OD员工,与人力服务公司签劳动合同,以派遣方式到华为工作,薪资待遇与华为内部员工基本一致,可通过考核转正。2.&nbsp;相关传言与真相华为相关人士称暂无官方回应,很多传言细节不准确。&nbsp;华为成都研究所员工透露,此次通报主要涉及成都研究所的数据存储部门,整个数据存储业务约100余人,此次明文通报除名辞退或通报批评的有62名,“很多部门基本全开除”&nbsp;。网传任正非亲赴成都、封楼抓人等消息不实。早在2024年年中,就有...
七安有出处嘛:省流:任正非亲赴成都等消息不实,2024 年年中就有人举报了;涉及36名违规当事人,其中有13人被除名;10人有主动申报情节或情节较严重的,予以辞退处理;另有13人被劝退、个人职级降3等。另外还有26名相关管理责任人作为直接或间接管理者,被处以个人职级降6等,冻结个人涨薪、职级晋升、干部向上任命,冻结期6—12个月不等;若下属违规偶发,则仅通报批评。并没有释放100HC😂😂😂
点赞 评论 收藏
分享
01-23 14:54
同济大学 Java
热爱敲代码的程序媛:给你提几点【专业技能】这个模块里面可优化的地方:1.【具备JVM调优经验】可以去b站上搜一下JVM调优的视频,估计一两个小时凭你的学习能力就能掌握JVM调优的实践方面的技能。2.【MySql优化】MySql这一栏,你去b站或者找个博客看看MySql优化,学一下,如果你本身比较熟悉MySql语句的话,那基本半天时间凭你的学习能力MySql语句优化方面的技能你也能掌握个差不多。以上1,2两点主要是因为我看你专业技能大部分都说的是偏理论,没有写应用。再就是最后,你结合你的项目,想一想你的项目中哪些sql语句是可以用MySql优化的,到时候你面试的时候也好结合着说一下。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务