我要招人

去企业版

首页 > 试题广场 >

给出一个整型数组，其中除了两个数字只出现一次之外，其他的数字

[问答题]

给出一个整型数组，其中除了两个数字只出现一次之外，其他的数字都出现了两次。请找出这两个只出现一次的数字。要求时间复杂度是 O(n) ，空间复杂度是 O(1) 。请简述思路。

牛客875188800号

第一步：利用a^a^b=0^b=b,把所有值异或一遍求出x^y

第二步：利用移位和奇数&1=1，偶数&1=0，找出为1的最低位为k

第三步：假设x在k位为1，则y在k位为0，再次遍历，若数在k位为1则与x异或，否则与y亦或，遍历完前者的结果为x^x^y=y,后者的结果为x^y^y=x

public class yuhuo {
    public static void main(String[] args) {
        int[] a= {1,2,1,4,5,7,5,4};//手动定义数组
        int[] b=soulution(a);//传回结果数组
        for(int arr:b){
            System.out.println(arr);
        }
    }
    public static int[] soulution (int[] a) {
        int m=0;
        for(int arr:a )  m^=arr;//求的所有数异或结果
        int k=0;//记录最低位出现1的位置
        while((m&1)==0){//利用若m最低位为1时，m&1=1，最低位为0时，m&1=0，来判定最低位的位置
           m=m>>1 ;
           k++;
        }
        int[] b={0,0};
       for(int arr:a){
           if(((arr>>k)&1)==1)//异或计算求其中一个值
               b[0]^=arr;
           else
               b[1]^=arr;//异或计算求其中另一个值
       }
        return b;
    }
}

发表于 2022-04-03 00:33:56 回复(0)

低调的斗士

public clas***ain{

    public static void main(String arg***r />         Integer a[] = {1,1,2,2,3,3,4,5,5,6};
        boolean flag ;
        for(int i = 0 ; i < a.length ; i ++){
            flag = true;
            l:for(int j = 0 ; j < a.length; j ++ ){

                if(a[i] == a[j] && i != j){
                    flag = false;
                    break l ;
                }
            }
            if(flag == true){
                System.out.println(a[i] );
            }
        }

    }

}

发表于 2019-05-19 11:40:49 回复(0)

灰鱼

对所有数字进行异或操作，得到的最后结果就是两个只出现一次的数字的异或；

这两个数字不相等，所有异或者结果中肯定至少有一位是1；

以这个为1的位为界，划分数组为这位为1和这位为0两组，分别做异或操作，得到的两个结果就是这两个数字

发表于 2020-03-26 11:18:42 回复(0)

gapex

/**
使用位运算
    先将所有数字异或后的结果保存在X中，接下来找到X最低位（从右向左数第一个）的1，这里假设X最低位的1的位于第k位；
    以第k位是否为1将所有数字分成两类，因为是二进制，所以第k位只有两种情况。由此，将所有数字分成了两类。可以确定（其实我也不懂为什么），两个出现一次的数字分别处于两类之中，也就是说，两个出现一次的数字不会全部属于同一类。
    按照“一个只出现一次的数字（其余数字出现两次)”的思路将两类中的数字分别全部异或，分别得到两类中只出现一次的数字，就是结果。
**/
vector<int> getOnce(vector<int> arr){
    vector<int> res;
    if(arr.size() == 0) return res;
    int num1, num2;
    num1 = num2 = 0;
    int xorAllRes = 0;
    for(auto iter = arr.begin();
        iter != arr.end();
        ++iter){
        xorAllRes ^= *iter;
    }
    int k = 0;
    while((xorAllRes & 1) == 0) ++k; //找到抑或结果最低位的1的位置，记录为k
    for(auto iter = arr.begin();
        iter != arr.end();
        ++iter){
        if(((*iter >> k) & 1) == 1){ //第k位为1，则为第"1"类，与num1异或
            num1 ^= *iter;
        }else{ //否则，属于第二类，与num2异或
            num2 ^= *iter;
        }
    }
    res.push_back(num1);
    res.push_back(num2);
    return res;
}

编辑于 2019-04-03 21:14:53 回复(0)

牛客227898193号

class Solution {
	vector<int> onlyones(vector<int>nums) {
	
		int count = 0;
		int i = 0;	
		int cur=nums[i];
		vector<int>res;
		while (i<nums.size()) {
			if (nums[i] == cur) { 
				count++;
				if (count == 2) {
					cur = nums[++i];
					count = 1;
				}
				i++;
			}
			else {
				res.push_back(cur);
				cur = nums[i++];
				count = 1;
			}
		}
		return res;
	}
};

发表于 2020-06-21 19:07:27 回复(0)

牛客419018875号

这个整型数组一定是排序好了的，因此可以用指针判定前后的值是否重复即可

发表于 2020-02-08 22:57:20 回复(0)

彭彭彭201903082029342

假设：该数组中出现的数字为a,a,b,b,c,c,d,e,f,f。两个只出现一次的数字是d,e。

1.将所有的数字异或起来，即a^a^...^d^e^f^f = d^e，得到d异或e的值x。

解释一下，x中为1的位即为d,e中不同的某个bit。接下来我们可以利用这一点，将整个数组分为两部分。

2.取x中为1的某一位，构成y。将y与所有的数进行异或运算，该位为0的分到一边，为1的分到一边。

解释一下，首先是y的构成举个例子：如果x为101。y可以取为100或者是1。如果，我们选择100。那么在分类的时候，我们就看异或结果第三位是否为1。取y为1时同理，看最后一位。

3.将两部分的值分别取异或，最后剩下的值就是d和e。

解释一下，将整个数组分为两部分以后，每部分都含有一个数字只出现一次，其他都出现两次。问题就转化为从一个数组中找出只出现了一次的数字。

发表于 2019-10-26 10:55:39 回复(0)

提交观点

问题信息

C++工程师 2019 Java工程师招商银行信用卡中心

上传者：小小

难度：

7条回答 90收藏 1291浏览

给出一个整型数组，其中除了两个数字只出现一次之外，其他的数字

问题信息

热门推荐

相关试题