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是一样的，代码更精简

参考资料

[1] 除k取余法的原理示意和代码实现(利用栈)

[2] 除k取余法的代码实现(考虑十六进制时的输出形式)

[3] C++定义动态数组