• <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.¢%

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

            題目描述:

            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個數中有且僅有一個數出現了奇數次(其它數都出現了偶數次),如何用線性時間常數空間找出這個數。

            解法如下:

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

            再看稍微加強版:

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

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

            1、異或所有元素得xors

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

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

            本題:

            思路類似于求解上題,關鍵是找出第一個來,然后借助上題結論求另外兩個

            // 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;
            }

            ?

            本文來自CSDN博客,轉載請標明出處:http://blog.csdn.net/yysdsyl/archive/2009/06/22/4289828.aspx

            久久国产精品无码HDAV| 久久久WWW成人免费毛片| 色综合久久夜色精品国产| 久久精品综合一区二区三区| 久久久久这里只有精品| 久久久噜噜噜久久中文字幕色伊伊 | 久久久国产精华液| 蜜臀久久99精品久久久久久| 国产A三级久久精品| 狠狠色丁香婷婷综合久久来来去 | 91精品国产91久久久久久青草 | 久久久久女教师免费一区| 久久久久女人精品毛片| 亚洲精品视频久久久| 精品综合久久久久久97超人| 亚洲中文字幕久久精品无码APP| a级毛片无码兔费真人久久| 久久亚洲精品成人AV| 久久久这里有精品| 久久乐国产精品亚洲综合| 久久精品一区二区三区不卡| 无遮挡粉嫩小泬久久久久久久 | 久久精品无码一区二区app| 久久亚洲欧美日本精品| 国产精品久久波多野结衣| 蜜臀久久99精品久久久久久小说| 久久中文字幕精品| 久久久久99这里有精品10| 午夜精品久久影院蜜桃| 亚洲精品tv久久久久久久久久| 热re99久久精品国产99热| 久久亚洲精品视频| 久久国产成人午夜aⅴ影院 | 国产福利电影一区二区三区久久老子无码午夜伦不 | 人妻丰满?V无码久久不卡| 日韩精品久久久久久免费| 久久精品国产久精国产一老狼| 久久免费视频1| 亚洲国产精品成人久久| 久久99久久99精品免视看动漫| 人妻无码中文久久久久专区|