位运算之找到落单的数（完整版）

给定一个数组，里边成k（k!=1）对存在任意整数，

任意个，只有一个整数只存在一次,找到它并且输出之。

tip：不进位加法的理解，假设十个十进制数做不进位加法，则最终结果为零，

由此k个k进制数相加 在加 单独一个数，最终为那个单独的数，在由

k进制转为对应的十进制数即可。

样例数组 arr 及 进制 k：

int[] arr = {

    2,2,2,9,

    7,7,7,3,

    3,3,3,6,

    6,6,6,0,

    0,0 

};

int k = 3;

（Java 代码如下）

public static void main(String[] args) {

int[] arr = {2,2,2,9,

    7,7,7,3,

    3,3,3,6,

    6,6,6,0,

    0,0 

};

int k = 3;

int len = arr.length;

//字符二维数组 存储每一个数的k进制的每一位上的数

char[][] kRadix = new char[len][];

int maxlen = 0;//k进制最大占位,其他不够的都补0

//每个数字的k进制字符串 翻转(低位到高位)，转为字符数组

for(int i = 0; i < len; i++) {

kRadix[i] = new StringBuilder

(Integer.toString(arr[i], k)).reverse().toString().toCharArray();

/**

* 字符二维数组的存储内容

* 2

* 2

* 2

* 001

* 12

* 12

* ...

*/

if(kRadix[i].length > maxlen) {

maxlen = kRadix[i].length;

}

}

//做不进位加法，每列正常求和，在对k取余

//每列字符相加，所以先遍历行

int[] resArr = new int[maxlen];

for(int i = 0; i < len; i++) {

for(int j = 0; j < maxlen; j++) {

if(j >= kRadix[i].length) {

resArr[j] += 0;

}else {

resArr[j] += kRadix[i][j] - '0';//转为int

}

}

}

int res = 0;

//每一列加和，对k 求余，并且转为10进制

//在把每一列相加，即为所求

for(int i = 0; i < resArr.length; i++) {

res += (resArr[i]%k) * (int)Math.pow(k, i);

}

System.out.println(res);

}