找到 50 億個(gè) 32 位整型數(shù)中出現(xiàn)重復(fù)的數(shù)。
可行的方法是利用位圖。32 位數(shù)的范圍是 0~2^32 - 1
開(kāi)辟一個(gè) 2^32 個(gè) bit 的空間，大小約為 512 MB。
一次掃描每一個(gè)數(shù)，檢測(cè)以該數(shù)為索引的那個(gè) bit 是否為 0 ，若為 0 ，則說(shuō)明過(guò)去不存在，將其置為 1，如果為 1 則說(shuō)明以前出現(xiàn)過(guò)，則說(shuō)明該數(shù)是重復(fù)出現(xiàn)的。
這個(gè)問(wèn)題解決的關(guān)鍵在于用待檢測(cè)數(shù)去做索引，利用隨即存取的特點(diǎn)，可以做到 O(1) 的效率。用數(shù)本身做索引是一種高效的方法。
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 }
關(guān)鍵在于這個(gè)位圖如何實(shí)現(xiàn)。STL 中有個(gè) bitset 就好可以做這個(gè)工作。
但是如果需要仔細(xì)實(shí)現(xiàn)一個(gè)該如何辦？也就是說(shuō)自己實(shí)現(xiàn)一個(gè) bitset
實(shí)現(xiàn)一個(gè)類似的 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
更進(jìn)一步學(xué)習(xí) bitset ，《STL 源碼剖析》中應(yīng)該有所介紹
關(guān)鍵是對(duì) 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 閱讀(496)
評(píng)論(2) 編輯 收藏 引用