m*********a
发帖数: 3299 | 1 Given an array of integers, every element appears three times except for
one. Find that single one. Your algorithm should have a linear runtime
complexity.
用额为空间的，建立一个hastable就行了，相同的数计数，返回计数是一个的值
int singleNumber(int A[], int n) {
unordered_mapnummap;
for (int i=0;i
nummap[A[i]]++;
for (auto it=nummap.begin();it!=nummap.end();it++){
if (it->second==1) return it->first;
}
}
但是如果只能用固定的额为空间的话，只能用位运算。
int是32位的数，每次把计数的位移到个位，然后计数，3的倍数的话，用%3清零，最后
得到就是要找的那个数的在这个位置的bit(0或1)。计数好后，移动到以前的bit位置，
用|总结所有的位。但是下面的程序的结果就是不对。不知道为啥？
int singleNumber(int A[], int n) {
int bits[32],res=0;
for (int i=0;i<32;i++){
bits[i]=0;
for (int j=0;j
if ((A[j]>>i)&1) bits[i]=(bits[i]+1)%3;
}
res|=(bits[i]<
}
return res;
} |
p*********j
发帖数: 47 | 2 正确的代码，请参考：
static int singleNumber(int A[], int n) {
int[] bits = new int[32];
int res = 0;
for (int i = 0; i < 32; i++) {
bits[i] = 0;
for (int j = 0; j < n; j++) {
bits[i] += (A[j] >> i) & 1;
bits[i] %= 3;
}
res |= (bits[i] << i);
}
return res;
} |
m*********a
发帖数: 3299 | 3 你的这个和我的是一样，我递交了leetcode都能通过。
居然通不过我的笔记本的测试，太让人抓狂了
但是第一个写的居然都能过测试。 其实Bit[i]是0的时候不用加了，加了和原来的数一样
【在 p*********j 的大作中提到】
: 正确的代码，请参考：
: static int singleNumber(int A[], int n) {
: int[] bits = new int[32];
: int res = 0;
: for (int i = 0; i < 32; i++) {
: bits[i] = 0;
: for (int j = 0; j < n; j++) {
: bits[i] += (A[j] >> i) & 1;
: bits[i] %= 3;
: }
|
f****n
发帖数: 208 | 4 int size might not be 32 bits on the running platform? |
r*****3
发帖数: 27 | 5 我用你的代码提交了一次leetcode 没错啊 0.0
【在 m*********a 的大作中提到】
: 你的这个和我的是一样，我递交了leetcode都能通过。
: 居然通不过我的笔记本的测试，太让人抓狂了
: 但是第一个写的居然都能过测试。 其实Bit[i]是0的时候不用加了，加了和原来的数一样
|
m*********a
发帖数: 3299 | 6 这个我知道了，我的电脑上通不过，估计是code::block的问题
code::block还不能用 for (auto it:myVector) cout<<*it;
【在 r*****3 的大作中提到】
: 我用你的代码提交了一次leetcode 没错啊 0.0
|
