程序员人生 网站导航

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

栏目:php教程时间:2015-06-11 08:14:42
#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; }
------分隔线----------------------------
------分隔线----------------------------

最新技术推荐