关于题型：从序列中找出现次数为k的数（待完成）

109 阅读 0 评论 72 点赞

我是靠谱客的博主斯文抽屉，这篇文章主要介绍关于题型：从序列中找出现次数为k的数（待完成），现在分享给大家，希望可以做个参考。

文章目录

- - - - 1.序列中的数都出现过偶数次，只有一个数出现过奇数次，求此数
      - 2.序列中的数都出现过偶数次，只有两个数出现过奇数次，求此数
      - 3.序列中的数都出现过奇数次，只有一个数出现过1次，求此数

1.序列中的数都出现过偶数次，只有一个数出现过奇数次，求此数

该题运用了异或运算，一个数异或自己等于零，而异或零等于自己，且异或运算满足交换律。所以将序列成员依次异或，相同的数会异或成零，最后的结果就是出现奇数次的那个数。

复制代码

1
2
3
4
5
6
7
8
 int singleNumber(int* A, int n) {
        // write code here
        int res = A[0];
        for(int i = 1;i<n;i++)
            res ^= A[i];
        return res;
}

2.序列中的数都出现过偶数次，只有两个数出现过奇数次，求此数

同上题，本题所求的是两个出现过偶数次的数，还是利用异或运算。设a和b是那两个出现奇数次的数，按上题的方法异或后，得到的值就是a^b。如1001与1011异或，得0010，为1的位即为两数值不同的位。
所以以这个为根据，如上例子，把序列分为两组，一组是第二位为1的数，而另一组是第二位为0的数。那么每组也就只有一个出现过奇数次的数了，转化为了题1的问题。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> getnum(vector<int> num){
		int a = 0,a2 = 0;
		vector<int> res;  
		for(int i = 0;i<num.size();i++)
			a ^= num[i];
		int rightone = a & (~a+1);   //这是取右边第一个1的方法
		for(int i = 0;i<num.size();i++)
			if(num[i]&right!=0)
				a2 ^= num[i];
		res.push_back(a2);
		res.push_back(a2^a);
		return res;
}