这是一个创建于 2001 天前的主题，其中的信息可能已经有所发展或是发生改变。
题目
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,3,2]
输出: 3
示例 2:
输入: [0,1,0,1,0,1,99]
输出: 99
题解
根据上一道题目的经验，我们很明确的知道不能用数数字的办法去解。考虑位运算的办法，找相关的性质。
这个题其实就是求，在其他数都出现 k 次的数组中有一个数只出现一次，求出这个数。
而上面那个 k 次的是有通用解法的。
使用一个 32 维的数组，用这个 32 维的数组存储:
[第 31 位 1 的总数， 第 30 位 1 的个数，…， 第 1 位 1 的个数]
-
假如第 0 位 1 的个数是 k 的倍数，那么要求的这个数在该位一定是 0 ；
-
若不是 k 的倍数，那么要求的这个数在该位一定是 1。
因为假如说数组中的某些数在该位置是 1，那么因为这个数要么出现 k 次，那么出现 1 次。
这样我们就可以找出只出现一次那个数的二进制表示形式。二进制如何转化为 10 进制呢？
假如，按照上面的规则，最招找到的二进制为:
A = [0, 0, 0, 0, 0, …, 1]
因为异或操作是：相同为 0，不同为 1。
那么久可以依次用 1, 2, 4, 8 … 和依次每一位异或，即可得到最终答案。
第二部分可能不好理解，可以手动模拟下。
class Solution {
public int singleNumber(int[] nums) {
// 有多少个相同的数字
int N = 3;
// [高位 1 的个数,...,低位 1 的个数]
int[] bitNum = new int[32];
for (int i = 0; i < nums.length; i++) {
int compare = 1;
int num = nums[i];
for (int j = bitNum.length - 1; j >= 0; j--) {
if ((compare&num) != 0) {
bitNum[j]++;
}
compare = compare << 1;
}
}
int compare = 1;
int res = 0;
for(int i = bitNum.length - 1; i >= 0; i--) {
if(bitNum[i] % N != 0) {
res = res ^ compare;
}
}
return res;
}
}
热门阅读
 |
1
stebest 2019-07-04 09:44:24 +08:00
最后一个循环 compare 没有左移
|
 |
2
iDontEatCookie 2019-07-04 09:52:52 +08:00
你这种做法很容易想到啊。看到过一个好玩的解法，两个相同的数可以通过异或用一个变量找到，用一个数字的每一位去存而不是再开一个数组。既然每一位只能存两种状态，那么 k 个相同的数就可以用 logk 个变量找到。
var singleNumber = function(nums) { let a = 0, b = 0; for (let x of nums) { b = (b ^ x) & ~a; a = (a ^ x) & ~b; } return b; }; |
 |
3
rain0002009 2019-07-04 10:26:29 +08:00
我的天 楼主的这种解法竟然是很容易想到的吗
作为一般人的思路不是应该 先从小到大排个序 然后 3 个 3 个这么一取 只要第一个和第二个不相等 第一个就是那个数 告诉我 不是只有我是这么想的 |
 |
4
azh7138m 2019-07-04 10:39:53 +08:00
@rain0002009 就是个简单地状态转移，当时刚学数电（工科简易版本），写出来就是大概这个样子
https://gist.github.com/muzea/a50a68397bb6936cb48d7e13d9a69f60 比最佳答案差得很多，主要是我不会化简状态（ |
 |
5
ryd994 2019-07-04 10:42:11 +08:00 via Android
@rain0002009 排序至少 nlogn 复杂度
|
 |
6
RicardoY 2019-07-04 10:50:42 +08:00 via Android  1
这个解法使用了额外的空间啊...
|
 |
7
honeyCream 2019-07-04 11:19:11 +08:00
线性的时间复杂度已经不符合了吧.应该只只能循环一次,你后面又加了一次循环.
|
 |
8
tidyoux 2019-07-04 11:30:41 +08:00
那不叫 32 维数组。
很容易搜到符合题目要求的解： int singleNumber(int A[], int n) { int ones = 0, twos = 0, xthrees = 0; for(int i = 0; i < n; ++i) { twos |= (ones & A[i]); ones ^= A[i]; xthrees = ~(ones & twos); ones &= xthrees; twos &= xthrees; } return ones; } [引用]( https://www.cnblogs.com/daijinqiao/p/3352893.html) |
 |
9
b00tyhunt3r 2019-07-04 11:50:03 +08:00 via iPad
32 维数组？ lz 知道 2 维数组啥样吗
|
 |
10
no1xsyzy 2019-07-04 12:46:29 +08:00
想了想写了个通用的
时间复杂度 O(n log k) 空间复杂度 O(log k) 其中 n 是数组的大小，k 是重复的个数 https://gist.github.com/no1xsyzy/8db2a861103289a45be254dd54f44d2c 每次使用 pattern 重新生成的话时间不变空间 O(1) |
 |
11
carlclone 2019-07-04 12:49:01 +08:00 via Android
@honeyCream 2On 也是 On 为什么不是线性
|
|
12
no1xsyzy 2019-07-04 13:02:29 +08:00
@honeyCream O(2*n) == O(n)
|
|
13
honeyCream 2019-07-04 13:35:08 +08:00
@carlclone 哈哈哈～好吧 我是想说最优的解法应该是 8 楼的 只循环一次😂
|
|
14
honeyCream 2019-07-04 13:35:29 +08:00
@carlclone 虽然我也不一定能写出来那种解法
|
|
15
honeyCream 2019-07-04 13:36:24 +08:00
@no1xsyzy 我的我的～我表述得有问题
|
 |
16
yutonliu 2019-07-04 16:49:21 +08:00
虽然是算法题 不过 php 两个函数 就能解决了
|
 |
17
lamada 2019-07-04 18:48:32 +08:00
这道题记得最佳解法是 异或
|
|
18
lamada 2019-07-04 18:49:16 +08:00
看错了，是三次
|
 |
19
faustellar 2019-07-04 20:45:41 +08:00
之前见过一个类似的,如果是二进制每个元素逐位异或解决问题
这里可以搞成三进制后,再定义一个异或(无进位加法)解决问题 |
 |
20
xml123 2019-07-04 20:47:41 +08:00 2
异或不就是模 2 加法，这里换成模 3 加法就行了啊
|
 |
23
EthanDon 2019-07-04 21:19:35 +08:00
模 3 加法，可以的
|
|
24
azh7138m 2019-07-04 21:35:17 +08:00
|
|
25
azh7138m 2019-07-04 22:11:33 +08:00
@Yyyye 看了楼上的模 3 加法我想起来了…….
o t 是 one 第一位 two 第二位的意思，其实就是实现了一个模 3 加法，所以算完只要把第一位的 one 返回出去就好了 就是 00 01 10 三个状态的转移 对于 one 假如高位不是 1，输入是 1，那就是 00 -> 01 就是 o^(*it) ，高位是 1 的时候，如果这次输入是 1，那么应该是 10 -> 00 就是 &(~(t&*it)) 这里对高位做了判断 对于 two 如果高位和输入都是 1，那么就是 10 -> 00，所以是 ~(t&(*it)) ，对于其他的情况，~(t&(*it)) 结果都是 1，就看低位会不会进位，所以是 o&*it，最后 |t 是，高位是 1 低位是 0 输入是 0 对应这个场景 oo 是因为我要先算 o，要保存一下 大概就是这么个意思，我记得是枚举出所有的情况，写到一个表上，然后画电路图（ 这玩意我记得拿逻辑门做汽车尾灯花式闪烁上用到过（ |
 |
26
churchmice 2019-07-04 23:47:24 +08:00 via Android 2
@azh7138m 卡诺图
|
|
28
azh7138m 2019-07-05 01:41:43 +08:00 via Android
@churchmice 好像是这个，唉都忘记了。。。
|
 |
29
qwertyegg 2019-07-05 01:42:31 +08:00
也写了个 solution
~~~ public class Solution137 { public int singleNumber(int[] nums) { int[] bits = new int[32]; for(int n : nums) addBits(n, bits); StringBuilder binarySB = new StringBuilder(); for(int i = 31; i >= 0; i--) { binarySB.append(bits[i] % 3); } return (int)Long.parseLong(binarySB.toString(), 2); } private void addBits(int n, int[] bits){ int i = 0; while(n != 0){ bits[i] += n % 2; i++; n = n >>> 1; } } } ~~~ |
|
30
qwertyegg 2019-07-05 01:42:58 +08:00
也写了个 solution(上面的 markdown 错了)
``` public class Solution137 { public int singleNumber(int[] nums) { int[] bits = new int[32]; for(int n : nums) addBits(n, bits); StringBuilder binarySB = new StringBuilder(); for(int i = 31; i >= 0; i--) { binarySB.append(bits[i] % 3); } return (int)Long.parseLong(binarySB.toString(), 2); } private void addBits(int n, int[] bits){ int i = 0; while(n != 0){ bits[i] += n % 2; i++; n = n >>> 1; } } public static void main(String[] args) { System.out.println(new Solution137().singleNumber(new int[]{-2,-2,1,1,-3,1,-3,-3,-4,-2})); } } ``` |
|
31
qwertyegg 2019-07-05 01:43:18 +08:00
orz，跪了！
|
 |
32
valleyboy 2019-07-05 18:43:30 +08:00 via Android
求和 取余 右移 数制转换 循环
|
Select Language