找唯一不出现三次而出现1次的数子O(n)位运算算法[通俗易懂]

全栈程序员-站长 • 2022年1月25日下午8:00 • 未分类 • 阅读 44

大家好，又见面了，我是全栈君。

之前两次那个是异或运算处理。这次以为也是类似。可是没想出来。

高富帅想出来了算法，转为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)

PS: 代码前面那些直接copy了圆神的代码：）

#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;}

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/116121.html原文链接：https://javaforall.net