首页 > 代码库 > 数字中所有数出现次数为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次,求出这个数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。