• <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>

            S.l.e!ep.¢%

            像打了激速一樣,以四倍的速度運(yùn)轉(zhuǎn),開(kāi)心的工作
            簡(jiǎn)單、開(kāi)放、平等的公司文化;尊重個(gè)性、自由與個(gè)人價(jià)值;
            posts - 1098, comments - 335, trackbacks - 0, articles - 1
              C++博客 :: 首頁(yè) :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理

            題目描述:

            Given an array of n integers, such that each number in the array appears exactly twice, except for three numbers (say a, b and c) which appear exactly once.

            In O(n) time and O(1) space find a,b and c.

            分析:

            先看這樣一道題:

            n個(gè)數(shù)中有且僅有一個(gè)數(shù)出現(xiàn)了奇數(shù)次(其它數(shù)都出現(xiàn)了偶數(shù)次),如何用線性時(shí)間常數(shù)空間找出這個(gè)數(shù)。

            解法如下:

            從頭到尾異或一遍,結(jié)果就是要求的那個(gè)數(shù)。(原理很清楚明了)

            再看稍微加強(qiáng)版:

            n個(gè)數(shù)中有且僅有兩個(gè)數(shù)出現(xiàn)了奇數(shù)次(其它數(shù)都出現(xiàn)了偶數(shù)次),如何用線性時(shí)間常數(shù)空間找出這個(gè)數(shù)。

            解法比較巧妙,主要思想是將元素分成兩組,每組中有且僅有一個(gè)數(shù)出現(xiàn)了奇數(shù)次(其它數(shù)都出現(xiàn)了偶數(shù)次),然后應(yīng)用上題的結(jié)論解答,至于如何分組,見(jiàn)下:

            1、異或所有元素得xors

            2、找出xors中不為0的一個(gè)bit位(通常從右向左找出第一個(gè)不為0的)

            3、以2中找到的bit位為sentinel,將數(shù)組分為兩組

            本題:

            思路類(lèi)似于求解上題,關(guān)鍵是找出第一個(gè)來(lái),然后借助上題結(jié)論求另外兩個(gè)

            // Let s = a ^ b ^ c.? We know that s not in (a, b, c),
            // since if s == a, say, then b ^ c == 0 and b == c.?
            // Let f(x) be the lowest bit where x differs from s.?
            // The algorithm computes flips = f(a) ^ f(b) ^ f(c),
            // since the numbers appearing an even number of times cancel.?
            // The variable flips has parity 1, so it is non-zero,
            // and lowbit(flips) is a bit where one or three of a, b, c
            // differ from s.? It can't be three, however, so the final
            // exclusive-or includes exactly one of a, b, c.

            代碼:

            #include <iostream>

            using namespace std;

            // get lowest different bit
            int lowbit(int x)
            {
            ??? return x & ~(x - 1);
            }

            // Given an array of n integers, such that each number
            // in the array appears exactly twice, except for two
            // numbers (say a and b) which appear exactly once.
            //
            // In O(n) time and O(1) space find a and b.
            // e.g.
            // { 2 3 3 2 4 6 4 7 8 8 }? ---> a/b = { 6 7}
            void Find2(int seq[], int n, int& a, int& b)
            {
            ??? ////XOR
            ??? int xors = 0;
            ??? for(int i = 0; i < n; i++)
            ??????? xors ^= seq[i];

            ??? ////get different bit
            ??? int diff = lowbit(xors);

            ??? ////
            ??? a = 0;
            ??? b = 0;
            ??? for(int i = 0; i < n; i++)
            ??? {
            ??????? if(diff & seq[i])
            ??????????? a ^= seq[i];
            ??????? else
            ??????????? b ^= seq[i];
            ??? }
            }


            // Given an array of n integers, such that each number
            // in the array appears exactly twice, except for three
            // numbers (say a, b and c) which appear exactly once.
            //
            // In O(n) time and O(1) space find a,b and c.
            // e.g.
            // { 2 3 3 2 4 6 4 7 8 8 1 }? ---> a/b = { 6 7 1}


            // Let s = a ^ b ^ c.? We know that s not in (a, b, c),
            // since if s == a, say, then b ^ c == 0 and b == c.?
            // Let f(x) be the lowest bit where x differs from s.?
            // The algorithm computes flips = f(a) ^ f(b) ^ f(c),
            // since the numbers appearing an even number of times cancel.?
            // The variable flips has parity 1, so it is non-zero,
            // and lowbit(flips) is a bit where one or three of a, b, c
            // differ from s.? It can't be three, however, so the final
            // exclusive-or includes exactly one of a, b, c.

            void Find3(int seq[], int n, int& a, int& b, int& c)
            {
            ??? ////XOR
            ??? int xors = 0;
            ??? for(int i = 0; i < n; i++)
            ??????? xors ^= seq[i];

            ??? ////
            ??? int flips = 0;
            ??? for(int i = 0; i < n; i++)
            ??????? flips ^= lowbit(xors ^ seq[i]);
            ??? flips = lowbit(flips);

            ??? ////get one of three
            ??? a = 0;
            ??? for(int i = 0; i < n; i++)
            ??? {
            ??????? if(lowbit(seq[i] ^ xors) == flips)
            ??????????? a ^= seq[i];
            ??? }

            ??? ////swap a with the last element of seq
            ??? for(int i = 0; i < n; i++)
            ??? {
            ??????? if(a == seq[i])
            ??????? {
            ??????????? int temp = seq[i];
            ??????????? seq[i] = seq[n - 1];
            ??????????? seq[n - 1] = temp;
            ??????? }
            ??? }

            ??? ////call Find2() to get b and c
            ??? Find2(seq, n - 1, b, c);
            }

            int _tmain(int argc, _TCHAR* argv[])
            {
            ??? int a,b,c;
            ??? int test1[] = { 2, 3, 3, 2, 4, 6, 4, 7, 8, 8 };
            ??? Find2(test1, 10, a, b);
            ??? cout<<"a = "<<a<<" , b = "<<b<<endl;

            ??? int test2[] = {1 , 2 , 3 };//{ 2, 3, 3, 2, 4, 6, 4, 7, 8, 8, 1 };
            ??? Find3(test2, 3, a, b, c);
            ??? cout<<"a = "<<a<<" , b = "<<b<<" , c = "<<c<<endl;
            ??? system("pause");
            ??? return 0;
            }

            ?

            本文來(lái)自CSDN博客,轉(zhuǎn)載請(qǐng)標(biāo)明出處:http://blog.csdn.net/yysdsyl/archive/2009/06/22/4289828.aspx

            久久久久97国产精华液好用吗| 久久久久久久综合日本亚洲| 亚洲国产成人久久综合一 | 亚洲第一极品精品无码久久| 一个色综合久久| 亚洲日本va午夜中文字幕久久| 久久精品国产福利国产琪琪| 久久精品无码一区二区三区日韩 | 97精品伊人久久久大香线蕉| 久久久久久亚洲精品无码| 久久久久亚洲AV无码专区桃色| 久久亚洲天堂| 久久丫忘忧草产品| 久久久无码一区二区三区| 精品乱码久久久久久久| 91精品免费久久久久久久久| 久久99精品久久久久久野外| 亚洲国产精品综合久久一线| 亚洲av日韩精品久久久久久a| 久久精品亚洲精品国产色婷| 曰曰摸天天摸人人看久久久| 久久久久亚洲精品无码网址 | 青青久久精品国产免费看| 久久精品桃花综合| 97久久超碰国产精品2021| 国产精品免费久久久久影院| 要久久爱在线免费观看| 无码精品久久久天天影视| 99久久婷婷国产一区二区| 国产精品久久婷婷六月丁香| 99久久99久久久精品齐齐 | 日本欧美国产精品第一页久久| 精品伊人久久大线蕉色首页| 久久国产精品一区二区| 久久综合鬼色88久久精品综合自在自线噜噜| 久久久久亚洲av成人网人人软件 | 三级片免费观看久久| 精品九九久久国内精品| 久久久无码精品亚洲日韩京东传媒 | 久久人人超碰精品CAOPOREN| 久久国产欧美日韩精品|