在其他数都出现k次的数组中找到只出现一次的数

题目

　　给定一个整型数组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;

    }