g*********e
发帖数: 14401 | 1 就是那个找只出现一次的数,其余数都出现三次.
网上找了stackoverflow里有个解法,但看不懂.有好心人给个解法吗? |
c********w
发帖数: 2438 | |
h*****n
发帖数: 38 | 3 跟上题一样想法，不是count数字，count每个bit出现了几次。 |
T*******e
发帖数: 4928 | 4 This is EPI problem 8.17.
int singleNumber(int A[], int n) {
if(!A||n<=0) return INT_MIN;
int ones=0, twos=0;
for(int i=0; i
int newOnes=(~A[i]&ones) | (A[i]&(~ones) & (~twos));
int newTwos=(~A[i]&twos) | (A[i]&ones&(~twos));
ones=newOnes, twos=newTwos;
}
return ones;
}
【在 g*********e 的大作中提到】
: 就是那个找只出现一次的数,其余数都出现三次.
: 网上找了stackoverflow里有个解法,但看不懂.有好心人给个解法吗?
|
d*k
发帖数: 207 | 5 Add my two cents...
mod的那个不容易想啊。我说个更直观的。
随机在数组中找一个数v。然后做类似快排的调整，使得数组中小于v的值都在左侧连续
放置，大于v的值都在右侧，等于v的都在中间。如果只有一个v，返回v。否则若大于v
的个数和小于v的个数必然有一个是3*m和3*m+1，在个数是3*m+1的部分递归查找。
平均时间复杂度O(n)，最坏n*2。
P.S.
Recruiter上周说我的case会送到HC，这两周出结果，求bless啊！！！！！
【在 g*********e 的大作中提到】
: 就是那个找只出现一次的数,其余数都出现三次.
: 网上找了stackoverflow里有个解法,但看不懂.有好心人给个解法吗?
|
p*****7
发帖数: 21 | 6 统计每一位1出现的总次数是否是3的倍数
【在 g*********e 的大作中提到】
: 就是那个找只出现一次的数,其余数都出现三次.
: 网上找了stackoverflow里有个解法,但看不懂.有好心人给个解法吗?
|
G**C
发帖数: 365 | 7 这样做复杂度多少？
【在 p*****7 的大作中提到】
: 统计每一位1出现的总次数是否是3的倍数
|
g*********e
发帖数: 14401 | 8
32O(N) > O(NlogN)
【在 G**C 的大作中提到】
: 这样做复杂度多少？
|
