• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            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 閱讀(498) 評論(2)  編輯 收藏 引用
            久久国产精品无| 国产精品美女久久久免费| 尹人香蕉久久99天天拍| 国产精品美女久久福利网站| 一97日本道伊人久久综合影院| 无码人妻久久一区二区三区| 久久久久免费精品国产 | 久久精品青青草原伊人| 99久久er这里只有精品18| 99久久免费国产精品| 思思久久99热只有频精品66| 久久精品国产亚洲网站| 精品综合久久久久久97| 亚洲午夜久久久精品影院| 国产成人久久精品一区二区三区 | 亚洲精品高清国产一线久久| 久久久精品一区二区三区| 精品久久久久久中文字幕大豆网 | 免费观看成人久久网免费观看| 久久亚洲国产最新网站| 国产毛片久久久久久国产毛片 | 精品久久人人做人人爽综合 | 国产国产成人久久精品| 国产午夜精品久久久久免费视| 漂亮人妻被中出中文字幕久久| 国产精品成人无码久久久久久 | 久久这里有精品| 久久人妻少妇嫩草AV无码蜜桃 | 狠狠色综合网站久久久久久久高清| 久久午夜电影网| 久久综合久久综合久久综合| 精品国际久久久久999波多野| 99久久精品免费看国产一区二区三区 | 久久久久久久久66精品片| 久久成人精品| 久久嫩草影院免费看夜色| 久久免费香蕉视频| 久久久精品国产| 久久亚洲欧美国产精品| 久久精品男人影院| 久久精品国产第一区二区|