原文章地址:http://blog.csdn.net/morewindows/article/details/12684497
首先看看题目要求:
数组A中,除了某一个数字x之外,其他数字都出现了三次,而x出现了一次。请给出最快的方法找到x。
这个题目非常有意思,在本人博客中有《位操作基础篇之位操作全面总结》这篇文章介绍了使用位操作的异或来解决——数组中其他数字出现二次,而x出现一次,找出x。有《【白话经典算法系列之十二】数组中只出现1次的两个数字(百度面试题)》这边文章介绍了分组异或的方法来解决——数组中其他数字出现二次,而x和y出现一次,找出x和y。而这个题目则是其他数字出现3次,x出现一次。
应该如何思考了?
前两篇文章是利用两个相同的数异或结果为0来计算的,但这个题目中其他数字是出现了3次,因此肯定不可以再使用异或了。
我们换一个角度来看,如果数组中没有x,那么数组中所有的数字都出现了3次,在二进制上,每位上1的个数肯定也能被3整除。如{1, 5, 1, 5, 1, 5}从二进制上看有:
1:0001
5:0101
1:0001
5:0101
1:0001
5:0101
二进制第0位上有6个1,第2位上有3个1.第1位和第3位上都是0个1,每一位上的统计结果都可以被3整除。而再对该数组添加任何一个数,如果这个数在二进制的某位上为1都将导致该位上1的个数不能被3整除。因此通过统计二进制上每位1的个数就可以推断出x在该位置上是0还是1了,这样就能计算出x了。
推广一下,所有其他数字出现N(N>=2)次,而一个数字出现1次都可以用这种解法来推导出这个出现1次的数字。
示范代码如下:
- // 【白 话经典算法系列之十七】<span style="color:#000000;font: 14px/23px arial; text- transform: none; text-indent: 0px; letter-spacing: normal; word- spacing: 0px; float: none; display: inline !important; white- space: normal; font-size-adjust: none; font-stretch: normal; -webkit- text-stroke-width: 0px;">数组中只出现一次的数</span>
- // by MoreWindows( http://blog.csdn.net/MoreWindows )
- // 欢迎关注http://weibo.com/morewindows
- #include <stdio.h>
- #include <string.h>
- int FindNumber(int a[], int n)
- {
- int bits[32];
- int i, j;
- // 累加数组中所有数字的二进制位
- memset(bits, 0, 32 * sizeof(int));
- for (i = 0; i < n; i++)
- for (j = 0; j < 32; j++)
- bits[j] += ((a[i] >> j) & 1);
- // 如果某位上的结果不能被整除,则肯定目标数字在这一位上为
- int result = 0;
- for (j = 0; j < 32; j++)
- if (bits[j] % 3 != 0)
- result += (1 << j);
- return result;
- }
- int main()
- {
- printf(" 【白话经典算法系列之十七】数组中只出现一次的数\n");
- printf(" -- by MoreWindows( http://blog.csdn.net/MoreWindows ) --\n");
- printf(" -- http://blog.csdn.net/morewindows/article/details/12684497 -- \n\n");
- const int MAXN = 10;
- int a[MAXN] = {2, 3, 1, 2, 3, 4, 1, 2, 3, 1};
- printf("%d\n", FindNumber(a, MAXN));
- return 0;
- }
相关推荐
数组中只出现一次的两个数字.md
java基础面试题数组中只出现一次的数字本资源系百度网盘分享地址
本文实例讲述了PHP查找数组中只出现一次的数字实现方法。分享给大家供大家参考,具体如下: 问题: 一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。 实现代码如下:...
# Python实现《剑指offer》 部分代码自己添加了一些测试用例, 或者自己添加了一些功能 1. 初级程序员注重算法和数据结构 2. 事先做好准备,对工作有热情 3. 面试过程放松。不要急于写代码,了解清楚所要解决的问题,...
请找出这两个只出现一次的数字。 # -*-coding:utf-8 -*- class Solution: def FindNumsAppearOnce(self, array): # 如果两个数相同,那么这两个数的异或操作就等于0 if len(array) > 1 count += 1 mask = 1 <...
请写程序找出这两个只出现一次的数字。 分析 要解这题需要对异或操作有比较深的理解。 依次将数组中所有元素进行异或得到a,即num1和num2的异或。然后取a中二进制为1的一个位置,找到原数组中所有该位为1的数字进行...
数组中唯一只出现一次的数字.md
56.数组中只出现一次的数字 Array 57.和为S的两个数字 Array 57.和为S的连续正数序列 Array 关注 58.翻转单词序列 String 58.左旋转字符串 String 59.滑动窗口的最大值 Queue 常考 60.n个骰子的点数 61.扑克牌...
定义一个方法传入一个 int 类型数组,输出这个数组中每一个数字及其出现的个数 例如 传入数组[1,2,2,2,3,3,4,4,4,4] 打印结果: 数字 1 出现了 1 次 数字 2 出现了 3 次…
数组中数字出现的次数 II在一个数组 nums 中除一个数字只出现一次之外,其他数字都出现了三次。示例 1:输出:4示例 2:输出:1int singleNum
40. 数组中只出现一次的两个数,而其他数都出现两次 41. 和为s的连续整数序列 42. 翻转字符串 43. n个骰子的点数及出现的概率 44. 扑克牌的顺子 45. 圆圈中最后剩下的数 46. 1+2+3+...+n的和 47. 不用加减乘除...
文章目录在其他数都出现偶数次的数组中找到出现奇数次的数整型数组中其他数都出现偶数次找到唯一出现奇数次的数题目算法思路相应代码整型数组中其他数都出现偶数次找到两个出现奇数次的数题目算法思路相应代码 ...
一个数组,仅有两个数字出现一次,其他都是两次,找出这两个数字 思路: 思路:还是和当时的那道题目一样,用HashMap记录每个数字出现的次数,返回唯一两个get为0的数,加个flag分开即可 整合以上思路后,源码如下:...
# 在一个数组中除了一个数字只出现1次外,其他均出现2次,求这个数字
程序员面试题100题(63)-数组中三个只出现一次的数字[算法].pdf,这是一份不错的文件
HashMap用桶的话会有一个问题,加入这个数组的取值范围是0~9999,数组的组成是{1,2,9998,2,1},我们为了把5个数中间单独出现的那一个数取出来
js代码-查找数组中重复出现的元素
遍历原数组,并将临时数组中对应的索引所在数加一, 以记录原数组中数出现的次数 遍历临时数组,找出原数组中出现频率最高的数的次数,并记录到count 中 遍历临时数组,选出众数并输出 ,众数就是临时数组的索引...
面试题56 - I. 数组中数字出现的次数题目链接面试题56 - I. 数组中数字出现的次数题目描述一个整型数组里除了两个数字之外,其他的数字都出现了两次。传出