【本文鏈接】
http://www.cnblogs.com/hellogiser/p/find-number-which-appears-1-time-while-the-remaining-numbers-appear-3-times.html
【題目】
數組A中，除了某一個數字x之外，其他數字都出現了三次，而x出現了一次。請給出最快的方法，找到x。
【分析】
分別統計每一個數字32bit出現1的次數，然後將所有數字對應bit的次數相加，得到的次數對3取余，出現3次的數字都在對3取余的過程中抵消掉了，剩下的次數即為x各位出現1的次數。
【代碼】
C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
// 60_FineNumberAppearOnceTheOthersAppear3Times.cpp : Defines the entry point for the console application.
//
/*
version: 1.0
author: hellogiser
blog: http://www.cnblogs.com/hellogiser
date: 2014/5/28
*/
#include "stdafx.h"
/*
1,1,1,2,2,2,3
001,001,001,
010,010,010
011
number of 1: 003+030+011 = 044
044 % 3 = 011 ===>3
*/
int FindNumberAppearOnce_WithTheOther3Times(int data[], int length)
{
if(NULL == data || length <= 0)
return -1;
const int N = 32;
// count the 1s of 32 bit
int counts[N] = {0};
for (int i = 0; i < length; ++i)
{
for (int j = 0; j < N; ++j)
{
counts[j] = (counts[j] + (data[i] >> j & 1)) % 3;
}
}
// get the result
int result = 0;
for (int j = 0; j < N; ++j)
result += (counts[j] << j);
return result;
}
void test_base(int data[], int length)
{
int result = FindNumberAppearOnce_WithTheOther3Times(data, length);
printf("%d \n", result);
}
void test_case1()
{
int data[] = {1, 1, 1, 2, 2, 2, 3};
int length = sizeof(data) / sizeof(int);
test_base(data, length);
}
void test_case2()
{
int data[] = {1, 1, 1, 2, 2, 2, 3, 3, 3, 4};
int length = sizeof(data) / sizeof(int);
test_base(data, length);
}
void test_main()
{
test_case1();
test_case2();
}
int _tmain(int argc, _TCHAR *argv[])
{
test_main();
return 0;
}
/*
3
4
*/
【參考】
http://blog.csdn.net/zhu_liangwei/article/details/11352999
http://ouscn.diandian.com/post/2013-10-06/40052170552
http://stackoverflow.com/questions/7338437/finding-an-element-in-an-array-that-isnt-repeated-a-multiple-of-three-times
http://www.sysexpand.com/?path=exercises/number-appearing-once-in-array-of-numbers-appearing-three-times
【本文鏈接】
http://www.cnblogs.com/hellogiser/p/find-number-which-appears-1-time-while-the-remaining-numbers-appear-3-times.html
