posts - 183,  comments - 10,  trackbacks - 0
找到 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.08.0 - t);
47         *|= 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 阅读(464) 评论(2)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理