題目

　　給定一個整型數組arr和一個大于1的整數k，已知arr中只有一個數出現了一次，其他的數都出現了k次，請返回只出現1次的數。要求時間復雜度O(N)，空間復雜度O(1)。

基本思路

　　首先看一個七進制數無進位相加的問題。?
　　七進制數a: 　　　　6 4 3 2 6 0 1?
　　七進制數b:　　　　?3 4 5 0 1 1 1?
　　無進制相加的結果:　?2 1 1 2 0 1 2

　　可以看出，a和b無進位相加，在i位置上的結果就是 (a[i] + b[i]) % 7。同理，k進制的兩個數相加，i位置上的值為 (a[i] + b[i]) % k。那么，如果k個相同的k進制數相加，相加的結果一定是每一位上都為0。

　　知道上述過程，解這道題就很容易了。首先將數組中每一個數都轉換成k進制數，如果一個元素出現了k次，那么k次相加以后一定為0。所以，設置一個變量e，初始化為0，將所有元素相加完后，e的值就是只出現一次的數的k進制形式，再將其轉換成10進制數就可以了。
?

public int onceNum(int[] arr,int k){int[] e = new int[32];for(int i=0;i!=arr.length;i++){setExclusiveOr(e,arr[i],k);}int res = getNumFromKSysNum(e,k);return res; }public void setExclusiveOr(int[] e,int value,int k){int[] curKSysNum = getKSysNumFromNum(value,k);for(int i=0;i!=e.length;i++){e[i] = (e[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[] e,int k){int res = 0;for(int i = e.length-1;i!=-1;i--){res = res*k + e[i];}return res;}

?

總結

以上是生活随笔為你收集整理的在其他数都出现k次的数组中找到只出现一次的数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。