1.6 出现k次与出现1次
2019-03-22 本文已影响0人
Aurochsy
Chapter1: 位运算的奇技淫巧
6. 出现k次与出现1次
题目
数组中只有一个数只出现了1次,其它的数都出现了k次,请输出只出现了一次的数。
其中k为用户输入
算法
解法1(使用位运算技巧)
使用 hashmap
效果是一样的,代码还更精简,这个稍后数据结构部分再了解
原理
k个k进制数不进位相加
结果是 0
解法
-
将这个数组中的数全部转为k进制
-
除k取余法(通用的计算方法)
将十进制数
N
除以k得到结果和其余数,将结果继续除以N得到下一个余数和新结果,循环直至结果为0将得到的余数逆序排列即为
N
转为k
进制的结果 -
java中有封装好的方法,直接使用
integer.toString(int i, int radix)
-
-
将这些数进行不进位加法(相当于
^
运算 或者 将按位加的后的数对k取模) -
将最终结果转换回十进制(通用的计算规则即可)
对于
k
进制的数N
,maxLen
为其位数,arr[i]
为N
高低位反转后的第i
位的数字比如对于8进制的3707,高低位反转后为7073,转换为十进制为
7x8^0+0x8^1+7^8^2+3x8^3
for(int i=0;i<maxLen;i++){ res+=resArr[i]* (int)(Math.pow(k,i));//将resArrs数组(相当于一个数)按位对k求余后,再将其由k进制转为10进制 }
代码(java版本)
如果用java的 integer.toString(int i, int radix)
转换方法的话,会返回去掉高位的0的字符串,这样转换后的数的位数可能不一样,就无法进行按位加法。所以需要
- 将字符串进行反转,相当于将高低位顺序调换,低位左对齐。
- 转为字符数组,高位补0进行按位加运算
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;
//int len=sizeof(arr)/sizeof(array[0]);//如果arr是字符数组,则长度还需-1,因为其末尾多了一个`\0`字符
char[][] kRadix=new char[len][];//记录进制转换后的字符数组
int k=3;//要转换的进制
int maxLen=0;//记录转换结果中的数字的最大位数
//转换为k进制数组
for(int i=0;i<len;i++){
//求每个数字的k进制字符串并翻转,然后转为字符数组
/*toString方法会将数字转为k进制的字符串,去掉高位的0。为了实现按位相加,需要将高低位顺序翻转,并转为字符数组,之后还要在高位补0*/
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)//当j>下一位的位数时
resArr[j]+=0; //高位补0
else
resArr[j]+=(kRadix[i][j]-'0');//kRadix字符数组-'0' 相当于将其由char转为int,再与resArr[j]运算
}
}
int res=0;//返回结果
for(int i=0;i<maxLen;i++){
res+=(resArr[i] % k) * (int)(Math.pow(k,i));//将resArrs数组(相当于一个数)按位对k求余后,再将其由k进制转为10进制
}
System.out.println(res);
}
代码(C++)
#include<iostream>
#include<cstdlib>
#include<stack>
#include<math.h>
using namespace std;
int main(){
int arr[16] = {2,2,2,11,7,7,7,3,3,3,6,6,6,0,0,0};//输入数组
int k = 3;//要转换的进制
int arrLen = sizeof(arr)/sizeof(arr[0]);//动态判断arr的长度
int resArr[10]={0};//存储所有元素按位相加后的、还未对k进行求余的、高低位逆序结果,这里限制转换结果的最高位数为10位 todo:可以考虑用动态数组
int result;//存储最终结果
for(int i=0;i<arrLen;i++){//对数组元素进行累加
int tmp=arr[i];//当前进行按位加运算的元素
for(int j=0;j<10;){//对当前元素进行按位加运算
while(tmp!=0){//除k取余法,将十进制转为k进制
resArr[j]+=(tmp%k);//tmp%k为逆序的第j位,result[j]存储数组所有元素的第j位的累加结果
tmp/=k;
j++;
}
if(j==9){
cout<<"预先定义的j太小了,小于转换后的数的最大位数"<<endl;
break;
}
}
}
for(int i=0;i<10;i++){
result+=(resArr[i] % k)*pow(k,i);//k进制转为10进制的通用算法
}
cout<<result<<endl;
}
解法2(使用HashMap)
就是对数组中出现的数作为 key
, 出现一次其 value
+1 ,效果和解法1是一样的,代码更精简
参考资料
[3] C++定义动态数组