位运算-出现k次与出现一次

Java基础

浏览数:148

2019-10-8

题目:数组中arr只有一个数出现了1次,其他的数都出现了k次,请输出这个只出现了一次的数。

思路:这道题目要求使用位运算实现,如果采用数据结构Map就会简单很多。解此题前先了解不进位加法的思想,比如两个二进制数10+10 进行不进位加法得到的结果是00(二进制),再比如10个51进行不进位加法结果也为00(十进制),这里就可以得出结论,如果K个相同的K进制数进行无进位加法,相加的结果一定是每一位上都为0的K进制数。那么这道题的思路就是,构造一个二位数组kRadix,其中一维索引是数组arr的长度,二位索引存的就是每个数字的三进制字符串再反转过后的字符数组,这里要反转的目的是因为数组arr转化成三进制数组时的长度不一样,反转过后的字符串高位补0,这样高低位就对齐了,这样才能进行不进位加法。然后对每一列采用不进位加法,将结果存进一个一维数组resArr,再然后遍历这个数组分别对K求余累加算出十进制,得出的数据就是唯一的那个数。

代码:

public class 出现K次 {

	public static void main(String[] args) {
		int []arr = {2,2,2,9,7,7,7,3,3,3,6,6,6,0,0,0};
		int len = arr.length;
		char [][] kRadix = new char[len][];
		int k = 3;
		// 转成k进制字符数组
		int maxLen = 0;
		// 对于每个数字
		for (int i = 0; i < len; i++) {
			// 求每个数字的三进制字符串并反转,然后转为字符数组
			kRadix[i] = new StringBuilder(Integer.toString(arr[i],k)).reverse().toString().toCharArray();
			if (kRadix[i].length>maxLen) {
				maxLen = kRadix[i].length;
			}
		}
		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'); // kRadix[i][j]-'0' 字符-'0'  从字符转换成了数字
				}
			}
		}
		int res = 0;
		for (int i = 0; i < maxLen; i++) {
			res += (resArr[i] % k ) * (int)(Math.pow(k, i));  // 累加求出十进制
		}
		System.out.println("数组中唯一出现的数字是:"+res);

	}

}

结果:

  

 

作者:|旧市拾荒|