当前位置:首页 » 面试笔试 » 正文

找出数组中有3个出现一次的数字

857 人参与  2019年06月04日 18:22  分类 : 面试笔试  评论

题目:

一个int数组中有三个数字a、b、c只出现一次,其他数字都出现了两次。请找出三个只出现一次的数字。

下面要来看下如果找出这个与另外两个数的该bit位不同的数。

先看第一种情况,如果a,b,c三个数中,有两个该bit位为0,另一个为1,我们遍历数组,分别统计该数组元素中该bit位为1和0的元素个数,分别设为count1和count0,并同时将所有该bit位为1的元素异或,所有该bit位为0的元素异或,得到的结果分别设为temp1和temp0。如果count1为奇数,则可能有两种情况,a,b,c三个数的该bit位全为1,或者有两个为0,一个为1,如果有temp0==0,则说明是前一种情况(a,b,c的该bit位全为1的话,所有该bit位为0的每个元素出现了两次,因此异或后的结果为0),即3个只出现一次的数均在第1类中,此时没法找出其中的一个数,则直接跳到下次循环,继续判断下一个bit位,如果temp0不等于0,则说明是后一种情况(说明该比bit位为0的元素异或后没有完全抵消,则说明在此类中有两个数字只出现一次),此时其中一个只出现一次的数字就在另一类中,值就是temp1(重复的元素异或后都抵消了)。同理:第二种情况也是类似的,如果 count0为奇数时,且temp1!=0时,则说明有两个值出现了一次的数在bit=1的这类中,另一个则在bit=0的那一类中,且值为temp0;

/*
一个int数组中有三个数字a、b、c只出现一次,其他数字都出现了两次。请找出三个只出现一次的数字。
*/

/*
思路:按照上面提供的思路,现在3个次数值出现一次的数字中找出其中一个,然后利用上篇博文中找出两个在数组只出现一次的数字的方法。
*/

#include<stdio.h>
#include<stdlib.h>
int xorArr(int *arr,int len){
    if(arr!=NULL&&len>0){
        int result=arr[0];
        for(int i=1;i<len;i++){
            result^=arr[i];
        }
        return result;
    }
}
/* 
返回a的最低位的1,其他各位都为0 
*/
int findFirstBit1Index(int a){
    return a&(-a);// 
}
/* 
判断a中特定的位是否为1,若特定的位为 1,则返回true; 
这里的要判断的特定的位由b确定, 
b中只有一位为1,其他位均为0,由FindFirstBit1函数返回, 
而a中要判断的位便是b中这唯一的1所在的位是否为1 
*/ 
bool isBit1(int a,int b){
    return a&b;
}
//函数功能:找出数组中只有两个只出现一次的数字。
void findTwoNumInArrayOnlyOnce(int *arr,int len,int *first,int *second){
    if(arr==NULL||len<2){
        return;
    }
    *first=0;
    *second=0;
    //第一步:将arr中所有的数异或。
    int xorResult=xorArr(arr,len); 
    //第二步:找到异或结果中最右边为1的下标。 
    int index=findFirstBit1Index(xorResult); 
    //第三步:根据index将arr分成两个子数组,每个子数组中只有一个数字的次数为1,其余都为两次 
    for(int i=0;i<len;i++){
        if(isBit1(arr[i],index)){//此子数组中:为1 
            *first^=arr[i];
        }
        else{
            *second^=arr[i];
        }
    } 
}
//函数功能:检测数字a在第i为是否为  1 
bool isBit1In_i(int a,int i){
    return a&(1<<i); //将1左移 i在进行与 
}
//函数功能:检测数字a是否为奇数。 
bool isOdd(int a){
    return a%2;
} 
void findThreeNumInArrayOnlyOnce(int *arr,int len,int *first,int *second,int *third){
    if(arr==NULL||len<3){
        return;
    } 
    *first=0;
    *second=0;
    *third=0; 
    //将全部数据为成两类,第一类bit=1,第二类bit=0
    int countBit=sizeof(int)*8;//每个int类型的整数所占的bit数
    int count1,count0;//分别用来保存第一类和第零类中的元素个数。 
    int temp1,temp0;//分别用来保存第一类和第零类中所有元素的异或结果。 
    for(int i=0;i<countBit;i++){
        count1=count0=temp1=temp0;//每次循环时清零 
        for(int j=0;j<len;j++){
            if(isBit1In_i(arr[j],i)){//检测arr[j]在第i为是否为1. 
                count1++;
                temp1^=arr[j];
            }
            else{
                count0++;
                temp0^=arr[j];
            }
        }
        if(isOdd(count1)) {//count1为奇数时 即出现第一种情况:有两个出现一次的数字该bit为 0,一个为1  的情况。或者全1  的情况。 
            if(temp0!=0){//则说明有两个 出现一次的数字在bit=0的类,另一个在bit=1的类中,且值为temp1. ,否则什么也不做。
                *first=temp1;
                //找到一个数之后,,将此数放在数组最后一个位置,然后在数组的前n+1的元素中寻找。,然后调用在数组中有两个数字出现一次的函数即可解决问题。
                arr[len]=temp1; 
                findTwoNumInArrayOnlyOnce(arr,len+1,second,third); 
                return;//返回即可。 
            } 
        }
        else{//count1为偶数,即出现第二种情况:有两个出现一次的数字该bit为 1,一个为0  的情况。 或者全0 的情况。
            if(temp1!=0){//则说明有两个 出现一次的数字在bit=1的类,另一个在bit=0的位,且值为temp0. ,否则什么也不做。 
                *first=temp0;
                arr[len]=temp0; 
                findTwoNumInArrayOnlyOnce(arr,len+1,second,third);
                return ;//返回即可。 
            } 
        }
    }
}
int main(void){
    int n;
    while(scanf("%d",&n)!=EOF&n>0){
        int *arr=(int *)malloc((n+1)*sizeof(int));//多开辟一个空间,将找到的第一个数加入到最后一个位置,使得,这个数在数组中出现两次,进而方便寻找后面两个只出现一次的数字。 
        if(arr==NULL){
            exit(EXIT_FAILURE);
        }
        int val;
        for(int i=0;i<n;i++){
            scanf("%d",&val);
            arr[i]=val;
        }
        int first,second,third;
        findThreeNumInArrayOnlyOnce(arr,n,&first,&second,&third);
        printf("%d %d %d\n",first,second,third); 
    } 
    return 0;
}


来源:我是码农,转载请保留出处和链接!

本文链接:http://www.54manong.com/?id=1284

程序员面试  

微信号:qq444848023    QQ号:444848023

加入【我是码农】QQ群:864689844(加群验证:我是码农)

<< 上一篇 下一篇 >>

网站分类

标签列表

最近发表

全站首页 | 数据结构 | 区块链| 大数据 | 机器学习 | 物联网和云计算 | 面试笔试

本站资源大部分来自互联网,版权归原作者所有!