首页 > 代码库 > 数字中所有数出现次数为k次,但有一个不为k次,求出这个数

数字中所有数出现次数为k次,但有一个不为k次,求出这个数

思路: 1.建立辅助数组arr[32],统计数组中数的相应位上1的总和

            2.如果要找的数在某个位i上不为0,则arr[i]对k取模肯定为0,否则表示要找的数在此位为1, s  +=  1<<i

代码如下:

  

int find(int *a, int len, int K)
{
    int arr[32] = {0};
    int i, j;
    for(i = 0; i < len; ++i)
        {
      unsiged int k = a[i];    -->负数右移补1,会出错,所以先变成unsigned int
       for(j = 0; j < 32; ++j)
        {
            arr[j] += ( (k >> j) & 1 );//这个用来求某个整数中1 的个数
        }
    }
    int result = 0;
    for(j = 0; j < 31; ++j)//计算数值
        {   
            if(arr[j] %K != 0)
            result += (1 << j);
        }
   if(arr[31] % K != 0)//符号位
          result = 0 - result;   
    return result;
}


-->相关题目变形:

    1.一组数个数4K+2,有一个数只出现2次,其他的都出现4次,找出这个数     -->直接调用上面算法

    2.一个数组中有2个数只出现一次,其他数都出现2次,找出这两个数:

                   1.对数组所以数异或,得到的结果是要找的2个数异或的结果

                   2.从异或的结果的数找到第一个位为1的位,则可知:要找的两个数,在这个位上,肯定一个为0,一个为1,

                   3.根据这个位将数组分为2组,一组此位都是0,一组此位都是1,然后在在两个分组内全部数异或,即可得到结果

   

                         


数字中所有数出现次数为k次,但有一个不为k次,求出这个数