内容简介:这题起初根本想不到.直到翻了leetcode.com的discuss.....然后我整个人都"awesome!!!!"地瞎叫了. 下面讲讲我学来的思路.这题本质上来讲,就是让我们做一个有限状态机(finite state machine)(瞎翻的).
这题起初根本想不到.直到翻了leetcode.com的discuss.....然后我整个人都"awesome!!!!"地瞎叫了. 下面讲讲我学来的思路.
概述
这题本质上来讲,就是让我们做一个有限状态机(finite state machine)(瞎翻的).
首先
- 一般看到这种题,我们第一反应是做状态记录,比如数字x出现了y次.然后从记录里查询出现了一次的数字.
- 但是 现在我们的空间复杂度被限制成了O(1),不可能对所有的64位二进制表示的整数进行统计次数.
于是
- 我们只能着眼于二进制上了.我们先将状态记录缩小到记录目标数字的每一个 二进制 上.
- 那么这题就会变成: 遍历所有数,一个二进制位出现 1 的次数对 3 取余是否为 1 ,若为 1 ,那么我们目标数字的这一位也就是 1 . (具体见下例)
比如
- [1,1,1,2] 他们转换成二进制就是[01,01,01,10],我们可以知道第一位(从右往左)的二进制总共出现了三次1,那么我们的目标结果在第一位就绝对不会是1,相对的第二位出现了一次1,那么我们的目标值在这一位就是1
实际上
- 这题我们也可以写64个变量(不知道数据量范围多大或者32位也可以?)记录每位的二进制1出现的次数,然后每一个对三取余最后得出的64个1与0再组成一个整数...不过思路本质离不开这里.
- 而且到这一步空间复杂度已经是O(1)了,毕竟一个定长数组.但是大佬就是不一样,非要用几个变量解决....
最后
- 我们要运用逻辑门的想法设计一个计数器.计数到3就回归0.对于每一个 二进制 位,出现了多少次1我们可以用两个二进制表示(因为这题只需要记录%3),00表示出现0次,01表示出现1此,10表示出现2次.这样就记录了三个状态,(题目中是出现三次,其实对于x次,我们也可以同理描述).如下
补充
- 建议此题可以补充一下逻辑代数相关知识,暂时不知道有什么好的文章,这里贴个百度百科.学习成本不高
介绍
a为高位,b为低位.两个一起表示一个两位二进制表示的数字(一个计数器)
计数器代表值 | a | b | 目标出现次数 |
---|---|---|---|
0 | 0 | 0 | 0 |
1 | 0 | 1 | 1 |
2 | 1 | 0 | 2 |
0 | 0 | 0 | 3 |
1 | 0 | 1 | 4 |
2 | 1 | 0 | 5 |
... | ... | ... | ... |
上面是我们计数器需要达成的目标,一个计数循环.学过数字电路的同学看到这里应该就知道怎么做了. 我们再进一步. 我们遍历数据,每来一个数据c(这里一个二进制)我们的a与b就要开始为c计数,那么有以下情况
a | b | c | 结果a | 结果b |
---|---|---|---|---|
0 | 0 | 0 | 0 | 0 |
0 | 1 | 0 | 0 | 1 |
1 | 0 | 0 | 1 | 0 |
上面比较容易明白,来的是0,那么我们不统计,原来a,b的统计结果不变
a | b | c | 结果a | 结果b |
---|---|---|---|---|
0 | 0 | 1 | 0 | 1 |
0 | 1 | 1 | 1 | 0 |
1 | 0 | 1 | 0 | 0 |
这里也比较容易明白,当来的是1,那么只要为其计数增加1就好. 接下来就是我们的重头戏了.开始设计逻辑门能让我们的计数器保持3个状态记录循环. 我们观察结果a,可以看到会使 结果a=1 的状态仅有 ( a为1 && b为0 && c为0 ) || (a为0 && b为1 && c为1) ,同理可以推出b的表达式.
故可得出公式结果a结果b的表达式: : 结果a = (a & ~b & ~c) + (~a & b & c) : 结果b = (~a & ~b & c) + (~a & b & ~c)
另外根据逻辑代数分配率公式也可以变成: : 结果b = ~a & (~b & c + b & ~c) = ~a & (b^c) //二进制进位逻辑 再然后根据上图 a , c , 结果b 三者的关系写出结果a的逻辑 结果a = a & ~c & (~结果b) + ~a & c & (~结果b) = (~结果b) & (a^c)
然后对实际int型数据做以上处理,就可完成我们的目标.(实际上可以把int看成是在维护一个二进制组成的数组a[i],b[i],c[i],i表示第i位.我们每次位运算操相当于对每一个i所在的三个元素进行操作,也就变成了上述单独描述一个二进制位时的情况.))
/** * 给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现了三次。找出那个只出现了一次的元素。 * 题目要求:你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗? * * 思路有点像是数字电路设计一个计数器.此题的情况就是为每一位二进制进行计数,计数三次归零,那么最后没有归零的数就是出现一次的那个数.设计思路与逻辑门电路设计一样. * * @author jxwww * @date 2018/8/30 */ public class No137 { /** * 如上所推 */ public static int singleNumber(int[] nums) { int a = 0, b = 0; for (int c : nums) { int tempA = (~a & b & c) + (a & ~b & ~c); b = (~a & ~b & c) + (~a & b & ~c); a = tempA; } return b; } /** * 如上所推,你也可以写成这样 */ public int singleNumber(int[] nums) { int a=0,b=0; for (int c : nums) { b = b ^ c & ~ a; a = a ^ c & ~ b; } return b; } public static void main(String[] args) { int[] nums = new int[]{0, 1, 0, 1, 0, 1, 99}; System.out.println(singleNumber(nums)); } } 复制代码
以上所述就是小编给大家介绍的《LeetCode 137.只出现一次的数字 II》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- leetcode136. 只出现一次数字
- LeetCode之只出现一次的数字-Swift
- 找出数组中第 k 大的数字及其出现次数
- 【Leetcode】137.只出现一次的数字 II
- [剑指offer题解][Java]数组中出现次数超过一半的数字
- LeetCode 136:只出现一次的数字 Single Number
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
计算机组成与设计硬件/软件接口
[美] David A.Patterson、John L.Hennessy / 郑纬民 / 机械工业出版社 / 2007-4 / 75.00元
《计算机组成与设计硬件:软件接口》(原书第3版)是计算机组成的经典教材。全书着眼于当前计算机设计中最基本的概念,展示了软硬件间的关系,并全面介绍当代计算机系统发展的主流技术和最新成就。同以往版本一样,《计算机组成与设计硬件:软件接口》(原书第3版)采用MIPS处理器作为展示计算机硬件技术基本功能的核心。书中逐条指令地列举了完整的MIPS指令集,并介绍了网络和多处理器结构的基本内容。将CPU性能和程......一起来看看 《计算机组成与设计硬件/软件接口》 这本书的介绍吧!