今天在 leetcode 上遇到了 137. Single Number II https://leetcode.com/problems/single-number-ii/description/ 这道题:
给定一个非空整数数组, 除了某个元素只出现一次以外, 其余每个元素均出现了三次. 找出那个只出现了一次的元素.(Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.)
Note: 你的算法应该具有线性时间复杂度. 你可以不使用额外空间来实现吗?(our algorithm should have a linear runtime complexity. Could you implement it without using extra memory?)
- Examples:
- Input: [0,1,0,1,0,1,99]
- Output: 99
刚开始看到这道题时候, 我是略微欣喜的, 因为脑子里蹦出的想法应该就是用位异或的方法解决. 然而事情并没有那么简单. 在草稿纸上模糊了快一个小时候, 我点开了 Discuss, 进入了投票数最高的回答:
这一点开不得了, 我的表情是这样的(睁大双眼的脸), 里面只有这寥寥几行代码:
- public int singleNumber(int[] A) {
- int ones = 0, twos = 0;
- for(int i = 0; i <A.length; i++){
- ones = (ones ^ A[i]) & ~twos;
- twos = (twos ^ A[i]) & ~ones;
- }
- return ones;
- }
上面的代码, 如果你看两眼就明白. 你可以大大的鄙视我了, 这篇文章可能不适合你, 但是我们还是交个朋友吧
开玩笑, 言归正传. 这时我点开了另一个回答 An General Way to Handle All this sort of questions. https://leetcode.com/problems/single-number-ii/discuss/43296/An-General-Way-to-Handle-All-this-sort-of-questions.?page=2 , 简直如沐春风. 该方法采用了数字逻辑电路里的计算, 来解决诸如此类的问题. 哈哈, 好歹我本科也是学过数电这门课的. 这篇回答短小精悍, 我也理解了半天, 下面主要介绍我的理解:
(正经脸)
这个方法核心思想是建立一个记录状态的变量, 此方法适用于其他所有元素出现 K 次, 求唯一一个元素出现 M 次的问题(every one occurs K times except one occurs M times). 对于 leetcode137 这个问题, K=3,M=1.
我们先讨论 K=2 的情况, 我们可以用所有元素做位异或的方法来得到只出现一次的数, 那是因为出现两次的数都通过异或把他们的所有位都置 0 了. 对于 K=2, 每个数的每一位, 只有两种情况(1 或 0), 我们可以列出这几种情况:
current | incoming | next |
---|---|---|
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
上面的真值表对于每个数的每一位来说, 由于异或具有交换律, 所以我们可以看成两两相同的数的每一位做异或, 自然都变成 0. 剩下一个数的每一位只能跟前面异或完的 0 做异或, 得到的就是他本身.
现在讨论 K=3 的情况. 如果能有一种 "类异或" 的运算, 使得 3 个相同的数做了这种位运算后变成 0 就好了, 这不就跟上面的情况一样了嘛! 哈哈, 请叫我们数学家.
我们要找的就是这种 "类异或" 的位运算. 由于 K=3, 要进行 3 次位运算后这一位才为 0, 那么我们是不是可以把一个数的每一位看成有三个状态呢? 嗯, 可以试试.
其实用三进制应该是可以解决的, 但是对于代码来说实在是不好理解. 那么我们只能人为的用二进制定义每一位的这三种状态了. 根据香农第一定理, 3 种状态需要两位二进制位表示 (哈哈, 原谅我故作玄虚). 我们用(00,01,10) 来分别表示每个数每一位的这三种状态, 且定义如下真值表:(该真值表的运算表示为)
current(a, b) | incoming(c) | next(a, b) |
---|---|---|
0, 0 | 0 | 0, 0 |
0, 1 | 0 | 0, 1 |
1, 0 | 0 | 1, 0 |
0, 0 | 1 | 0, 1 |
0, 1 | 1 | 1, 0 |
1, 0 | 1 | 0, 0 |
来理解一下上面这个真值表, 每一位用虚拟的两位二进制 (a, b) 表示. 假设我们把每一位的初始状态都定为(a', b'), 如果接下来进行运算的 incoming 是三个一样的数, 那么第三次运算后的结果必定还是(a', b').
下面就要用到数字逻辑电路的知识了: 根据真值表写出逻辑式.
(其实不难: 对于 a, 把 next 中 a=1 对应的行组合选出来, 对于每一个组合, 凡取值为 1 的变量写成原变量, 取值为 0 的变量写成反变量, 各变量相乘后得到一个乘积项; 最后, 把各个组合对应的乘积项相加, 就得到了相应的逻辑表达式. 对于 b 同理)
所以:
- \(a = a\overline{b}\overline{c} + \overline{a}bc\)
- \(b = \overline{a}b\overline{c} + \overline{a}\overline{b}c\)
根据这两个逻辑式写出相应的 python 代码:
- a = (a&~b&~c)|(~a&b&c)
- b = (~a&b&~c)|(~a&~b&c)
ps: 这三种状态我们定义 00 表示真实位 0, 01 和
10
表示真实位 1, 所以有如下映射关系:
01 10 => 1 00 => 0
所以, 对于最后的结果, 我们只需要 return a|b 即可得到该位是 0 还是 1.
最后的 python 代码:
- class Solution:
- def singleNumber(self, nums):
- """
- :type nums: List[int]
- :rtype: int
- """
- a = 0
- b = 0
- for c in nums:
- a, b = (a&~b&~c)|(~a&b&c), (~a&b&~c)|(~a&~b&c)
- return a|b
但是, 上述代码放在 leetcode 中, 只 beats 掉了 30% 的人. 几个原因吧:
逻辑式可以化简.
确实还有对于这道题更简单但是不通用的方法
不过, 现在你已经可以解决所有类似的题目了, 惊喜吧!
来源: https://www.cnblogs.com/bjwu/p/9323808.html