找到 50 亿个 32 位整型数中出现重复的数。
可行的方法是利用位图。32 位数的范围是 0~2^32 - 1
开辟一个 2^32 个 bit 的空间，大小约为 512 MB。
一次扫描每一个数，检测以该数为索引的那个 bit 是否为 0 ，若为 0 ，则说明过去不存在，将其置为 1，如果为 1 则说明以前出现过，则说明该数是重复出现的。
这个问题解决的关键在于用待检测数去做索引，利用随即存取的特点，可以做到 O(1) 的效率。用数本身做索引是一种高效的方法。
1 #include <iostream>
2 #include <bitset>
3 #include <vector>
4 #include <cmath>
5 using namespace std;
6
7 void foo(const vector<int>& arr)
8 {
9 bitset<1024> bs;
10
11 for (vector<int>::size_type i = 0; i != arr.size(); ++i)
12 {
13 if (bs[arr[i]] == 0)
14 {
15 bs[arr[i]].flip();
16 }
17 else
18 {
19 cout << arr[i] << endl;
20 }
21 }
22 }
23
24 int main()
25 {
26 vector<int> arr;
27 for (int i = 0; i < 100; ++i)
28 {
29 arr.push_back(i);
30 }
31 arr.push_back(5);
32 arr.push_back(25);
33
34 foo(arr);
35 return 0;
36 }
关键在于这个位图如何实现。STL 中有个 bitset 就好可以做这个工作。
但是如果需要仔细实现一个该如何办？也就是说自己实现一个 bitset
实现一个类似的 bitset
http://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.2/bitset-source.html
http://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.2/bitset.html
http://blog.sina.com.cn/s/blog_4d3a41f40100kxnw.html
http://blog.sina.com.cn/s/articlelist_1295663604_0_1.html
更进一步学习 bitset ，《STL 源码剖析》中应该有所介绍
关键是对 bit 的读写如何操作。
1 #include <iostream>
2 #include <bitset>
3 #include <vector>
4 #include <cmath>
5 using namespace std;
6
7 template <unsigned NUM>
8 class MyBitset
9 {
10 private:
11 char* data_;
12 unsigned numbits;
13 unsigned numchars;
14 public:
15 MyBitset() : numbits(NUM), numchars(NUM / 8 + 1)
16 {
17 data_ = new char[numchars];
18 if (data_ == 0)
19 {
20 exit(1);
21 }
22 memset(data_, 0, numchars);
23 }
24 unsigned operator [] (unsigned pos)
25 {
26 char c = data_[pos / 8];
27 unsigned t = pos - pos / 8 * 8;
28 while (t > 0)
29 {
30 c <<= 1;
31 --t;
32 }
33 if (c & 128)
34 {
35 return 1;
36 }
37 else
38 {
39 return 0;
40 }
41 }
42 void set(unsigned pos)
43 {
44 char* p = data_ + pos / 8;
45 unsigned t = pos - pos / 8 * 8;
46 char temp = pow(2.0, 8.0 - t);
47 *p |= temp;
48 }
49 };
50
51 void foo(const vector<int>& arr)
52 {
53 // bitset<1024> bs;
54 MyBitset<1024> bs;
55
56 for (vector<int>::size_type i = 0; i != arr.size(); ++i)
57 {
58 if (bs[arr[i]] == 0)
59 {
60 // bs[arr[i]].flip();
61 bs.set(arr[i]);
62 }
63 else
64 {
65 cout << arr[i] << endl;
66 }
67 }
68 }
69
70 int main()
71 {
72 vector<int> arr;
73 for (int i = 0; i < 100; ++i)
74 {
75 arr.push_back(i);
76 }
77 arr.push_back(5);
78 arr.push_back(25);
79
80 foo(arr);
81 return 0;
82 }
posted on 2011-06-16 17:17
unixfy 阅读(487)
评论(2) 编辑 收藏 引用