算法-找出其他出现偶数次的数组中出现1次,2次,3次的数

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <iostream>
#include<vector>
#include<string>
#include<set>
#include<unordered_set>
#include<queue>
#include<map>
using namespace std;

//1。 找出1个出现1个次的数
/*
思路就是用异或,异或的作用能够将bit位相同的1,1 0,0变成0
这正好与偶数的思路相应。把所有数异或起来,就会发现,只出现1次的数上面的1的bit位才会被保存。
*/

int findone(int a[],int n)
{
int ans = 0;
for (int i = 0; i < n; i++)
{
ans ^= a[i];
}
return ans;
}

//2。找出两个出现1次的数
/*
出现两个1次的数再用1的方法就不起效了,但是有1种办法,就是把全部数组分成两部份。
每部份包括1个数,这样就能够转换为求出现1次数的方法。
如何分解呢,首先需要找出这两个数的区分:
a: 0 0 1 1
b: 0 1 0 1
异或:0 1 1 0
我们会发现a和b的比特位异或,有4种情况,其中两种情况结果是1.当结果比特位异或等于1的时候,a和b的比特位肯定不同。
这就是区分,我们可以通过找某1位比特位是不是为1来辨别成2个组。
*/

int findbit1(int n)
{//找出低位开始第1个为1的比特位,其他清0
return n&~(n - 1); // n&-n也能够
}
void findtwo(int a[],int n)
{
int ans1 = 0, ans2 = 0;
int flag = findone(a, n); //全部异或,结果=a^b 其他变成0;
flag = findbit1(flag);
for (int i = 0; i < n; i++)
{
if (a[i] & flag)
ans1 ^= a[i];
else
ans2 ^= a[i];
}
cout << ans1 << endl;
cout << ans2 << endl;
}

//3。找出3个出现1次的数
/*
这次更加困难了,由于没法直接划分成2组。 比如a,b,c
a 0 0 0 0 1 1 1 1
b 0 0 1 1 0 0 1 1
c 0 1 0 1 0 1 0 1
r 0 1 1 0 1 0 0 1
当结果为1的时候a,b,c有两种可能,1种是0 0 1 还有1种是 1 1 1这就没法辨别是哪一种情况了,比较辣手
网上有种方法是不管372101,先按 0 0 1这类情况算,然后得出的ans1和ans2比较 再分多种情况,比较复杂。
下面这类用到了反证法还有函数构造进程比较复杂,如果理解了,直接就噜出来了,比较推荐
1. 首先异或所有数 x=a^b^c.....其他异或=0
2. 再次用x异或所有数 x^a[i] 。 这样对出现偶数次的没有区分,由于我们不关心他们的实际大小
但是 x^a, x^b , x^c 这3个数 就起到了很大的变化。我们的目标是将这3个数划分成唯1的两组。
我们会发现 x^a ^ x^b ^ x^c =0, 而且3个数都不可能为0,而且互不相同。(由于x^a=b^c,b不等于c所以b^c不等于0)
然后做1个技能,令 n1=f(x^a),n2=f(x^b),n3=f(x^c),ni=f(x^a[i]) 其中f的作用是保存低位最近那个1其他全为0 ( XXXXX1000变成 000001000)
然后n1,n2,n3中就都有且只有1个位为1,现在区分n1,n2,n3的问题又成为
n1 0 0 0 0 1 1 1 1
n2 0 0 1 1 0 0 1 1
n3 0 1 0 1 0 1 0 1
r 0 1 1 0 1 0 0 1
之前是3个数可能同时为1,也可能只有1个为1,这样r=1; 但是3个数不可能同时为1. 不然与n1^n2^n3=0矛盾(由于x^a ^ x^b ^ x^c =0保证了任意1位上不可能3个1)
终究:
只需要 p=f(n1^n2^n3) 挑选 p&f(x^a[i])!=0 为1组 ==0为1组就好了
*/

void findthree(int a[], int n)
{
int x = findone(a, n);
int p = 0;
for (int i = 0; i < n; i++)
p ^= findbit1(x^a[i]);
p = findbit1(p);
int ans1 = 0, ans2 = 0, ans3 = 0;
for (int i = 0; i < n; i++)
{
if (p&findbit1(x^a[i]))
ans1 ^= a[i];
}
cout << ans1 << endl;
//将ans1踢出
for (int i = 0; i < n; i++)
{
if (ans1 == a[i])
{
swap(a[i], a[n - 1]);
break;
}
}
findtwo(a, n - 1);
}
int main(){

int a1[] = { 1, 1, 2, 2, 3, 4, 4 };
int a2[] = { 1, 1, 2, 2, 3, 4, 4 ,5};
int a3[] = { 6, 1, 1, 2, 2, 3, 4, 4, 5 };
cout << "找1个" << endl;
cout << findone(a1, sizeof(a1) / sizeof(int))<<endl;
cout << "找两个" << endl;
findtwo(a2, sizeof(a2) / sizeof(int));
cout << "找3个" << endl;
findthree(a3, sizeof(a3) / sizeof(int));
getchar();
getchar();
return 0;
}

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » 算法-找出其他出现偶数次的数组中出现1次,2次,3次的数

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡