首页 > 代码库 > 找唯一不出现三次而出现1次的数子O(n)位运算算法
找唯一不出现三次而出现1次的数子O(n)位运算算法
之前两次那个是异或运算处理,这次以为也是类似,但是没想出来。
高富帅想出来了算法,转为bitset,然后加起来 相同的话 要么0+0+0 要么1+1+1,最后剩下的 可以通过%3 算出0 或1,思想是这样,
其实也是bit运算,只不过不是异或这种一次运算O(1)这种,但是由于输入是int数组,-2^31~2^31-1 所以用32bit就可以表示了。
之前遇到,过几次错误,包括分配存储空间的问题,正如fawks说的,用全局数组,是在全局区域,比栈空间大很多,所以可以申请大数组,但是leetcode向来
不给数据范围的,不过从int也可以知道了,但是leetcode是class的,public成员貌似也是栈,结果出错,顺便说一下leetcode很多WA都说成TLE。。。还有其他的类型指定错误。。
后来发现有个负数的问题,负数取模符号位是异或(-7/-4=1.....-3, -7/4=-1....-3, 7/-4=-1.....3, 7/4=1....3 因此也可以归纳出,商的符号是除数被除数异或,余数符号是被除数符号),于是这样数组就变成负数了,为了便于处理,都辩证,但是最后符号位怎么判呢? 其实都当成数组处理,3m个1,3n个1 还有一个0/1,
加起来取模照样把代表符号位的0 1取出来。
但是从报错问题来看,还有一个-2^31出错了,后来想想是的, 符号位变1,然后后面变为10000 1+31个0 结果那个1都装不下了,于是他的补码是10000000,所以要专门处理,
这里实现了比较底层的,实现了补码。
处理好逻辑后提交,终于过了T T
高富帅想出来了算法,转为bitset,然后加起来 相同的话 要么0+0+0 要么1+1+1,最后剩下的 可以通过%3 算出0 或1,思想是这样,
其实也是bit运算,只不过不是异或这种一次运算O(1)这种,但是由于输入是int数组,-2^31~2^31-1 所以用32bit就可以表示了。
之前遇到,过几次错误,包括分配存储空间的问题,正如fawks说的,用全局数组,是在全局区域,比栈空间大很多,所以可以申请大数组,但是leetcode向来
不给数据范围的,不过从int也可以知道了,但是leetcode是class的,public成员貌似也是栈,结果出错,顺便说一下leetcode很多WA都说成TLE。。。还有其他的类型指定错误。。
后来发现有个负数的问题,负数取模符号位是异或(-7/-4=1.....-3, -7/4=-1....-3, 7/-4=-1.....3, 7/4=1....3 因此也可以归纳出,商的符号是除数被除数异或,余数符号是被除数符号),于是这样数组就变成负数了,为了便于处理,都辩证,但是最后符号位怎么判呢? 其实都当成数组处理,3m个1,3n个1 还有一个0/1,
加起来取模照样把代表符号位的0 1取出来。
但是从报错问题来看,还有一个-2^31出错了,后来想想是的, 符号位变1,然后后面变为10000 1+31个0 结果那个1都装不下了,于是他的补码是10000000,所以要专门处理,
这里实现了比较底层的,实现了补码。
处理好逻辑后提交,终于过了T T
时间复杂度 O(32n)=O(n),空间复杂度O(1)
#include <map> #include <set> #include <queue> #include <stack> #include <math.h> #include <time.h> #include <stdio.h> #include <stdlib.h> #include <iostream> #include <limits.h> #include <string.h> #include <string> #include <algorithm> #include <sstream> #include <iomanip> #define Min(a,b) (((a) < (b)) ? (a) : (b)) #define Max(a,b) (((a) > (b)) ? (a) : (b)) #define read freopen("in.txt","r",stdin) #define write freopen("out.txt","w",stdout) using namespace std; //#define MAXBITNUM 32 //#define MAXNUM 100000 //int bitnumvec[MAXNUM][MAXBITNUM]; int singleNumber(int A[], int n) { //vector<int*> vec; if(n==1) return A[0]; const int MAXBITNUM=32; //int bitnumvec[MAXNUM][MAXBITNUM]; int** bitnumvec=new int*[n]; for(int i=0;i<n;i++) bitnumvec[i]=new int[MAXBITNUM](); for(int i=0;i<n;i++) { int offset=MAXBITNUM-1; if(A[i]==-pow(2.0,31))//-2^31 { bitnumvec[i][0]=1;//, 10000000...000 } else//others { if(A[i]<0&&A[i]>-pow(2.0,31))//negative { bitnumvec[i][0]=1;//1 means negative, 0 means positve A[i]=-A[i]; } while(A[i]!=0) { bitnumvec[i][offset]=A[i]%2; //bitnum[offset]=A[i]%2; A[i]=A[i]/2; offset--; } } //reverse(vec.begin(),vec.end()); //vec.push_back(bitnum); } //memset(bitnum,0,sizeof(int)*MAXBITNUM); int bitnum[MAXBITNUM]; memset(bitnum,0,sizeof(int)*MAXBITNUM); int x=0; for(int i=0;i<MAXBITNUM;i++) { //if(i==MAXBITNUM-1) // int y=1; for(int j=0;j<n;j++) { //if(bitnumvec[j][0]==0) bitnum[i]+=bitnumvec[j][i]; //else if(bitnumvec[j][0]==1) // bitnum[i]-=bitnumvec[j][i]; } bitnum[i]=bitnum[i]%3; if(i>0) x+=bitnum[i]*pow(2.0,MAXBITNUM-1-i); } if(bitnum[0]==1 &&x !=0) x=-x; else if(bitnum[0]==1 && x==0) x=-pow(2.0,31); //for(int i=0;i<MAXBITNUM;i++) //int x; //for(int i=0;i<MAXBITNUM;i++) for(int i=0;i<n;i++) delete[] bitnumvec[i]; delete[] bitnumvec; return x; } int main() { //int x=-3%2; int a[]={-2,-2,-2147483648,-2}; cout<<singleNumber(a,4)<<endl; return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。