内容简介:这题起初根本想不到.直到翻了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
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Programming Amazon Web Services
James Murty / O'Reilly Media / 2008-3-25 / USD 49.99
Building on the success of its storefront and fulfillment services, Amazon now allows businesses to "rent" computing power, data storage and bandwidth on its vast network platform. This book demonstra......一起来看看 《Programming Amazon Web Services》 这本书的介绍吧!