本文共 1283 字,大约阅读时间需要 4 分钟。
参考自程序员代码面试指南
给定一个整型数组,和一个大于1的整数k,已知arr中只有一个数出现了一次,其他的数都出现了k次,请返回只出现一次的数。
要求:时间复杂度为O(N),额外空间复杂度为O(1);
下面的例子是两个七进制数的无进位相加:
a: 6 4 3 2 6 0 1
b: 3 4 5 0 1 1 1
r: 2 1 1 2 0 1 2(结果)
两个七进制的a和b,在i位上无进位相加的结果就是(a(i)+b(i))%7,同理,k进制的两个数,第i位上无进位相加的结果就是(c(i)+d(i))%k。那么,如果k个相同的k进制数进行无进位相加之,相加的结果一定是每一位上都为0的k进制数。
首先设置一个变量eO,它是一个32位的k进制整数,且每个位置都是0,然后遍历arr,把遍历到的每一个整数都转换为k进制数,然后与eO进行无进位相加,遍历结束时,把32位的k进制整数eORes转换为10进制数,就是我们想要的结果。因为k个相同的k进制数无进位相加,结果一定是每个位都为0的k进制整数,所以只出现一次的那个数最终就会被剩下来。
public int onceNum(int[] arr,int k){ int[] eO=new int[32]; for(int i=0;i!=arr.length;i++){ setExclusiveOr(eO,arr[i],k); } int res=getNumFromKSysNum(eO,k); return res; } public void setExclusiveOr(int[] eO,int value,int k){ int[] curKSysNum=getKSysNumFromNum(value,k); for(int i=0;i!=eO.length;i++){ eO[i]=(eO[i]+curKSysNum[i])%k; } } public int[] getKSysNumFromNum(int value,int k){ int[] res=new int[32]; int index=0; while(value!=0){ res[index++]=value%k; value=value/k; } return res; } public int getNumFromKSysNum(int[] eO,int k){ int res=0; for(int i=eO.length-1;i!=-1;i--){ res=res*k+eO[i]; } return res; }
转载地址:http://bryai.baihongyu.com/