青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

S.l.e!ep.¢%

像打了激速一樣,以四倍的速度運轉(zhuǎn),開心的工作
簡單、開放、平等的公司文化;尊重個性、自由與個人價值;
posts - 1098, comments - 335, trackbacks - 0, articles - 1
  C++博客 :: 首頁 :: 新隨筆 :: 聯(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個數(shù)中有且僅有一個數(shù)出現(xiàn)了奇數(shù)次(其它數(shù)都出現(xiàn)了偶數(shù)次),如何用線性時間常數(shù)空間找出這個數(shù)。

解法如下:

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

再看稍微加強版:

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

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

1、異或所有元素得xors

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

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

本題:

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

// 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博客,轉(zhuǎn)載請標明出處:http://blog.csdn.net/yysdsyl/archive/2009/06/22/4289828.aspx

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            亚洲精品一区二区三区福利| 亚洲黄一区二区| 亚洲一区三区视频在线观看 | 欧美大片免费久久精品三p| 久久超碰97人人做人人爱| 国产日韩综合| 欧美高清hd18日本| 欧美伦理91i| 欧美专区日韩专区| 老牛嫩草一区二区三区日本| 亚洲精品日韩综合观看成人91| 最新高清无码专区| 国产精品私人影院| 欧美v亚洲v综合ⅴ国产v| 欧美理论电影网| 久久国产精品毛片| 欧美激情va永久在线播放| 午夜精品www| 麻豆精品一区二区av白丝在线| 99精品热6080yy久久| 亚洲欧美亚洲| 日韩午夜在线视频| 欧美一级视频免费在线观看| 亚洲精选中文字幕| 欧美在线视频一区| 亚洲少妇自拍| 久久久久久香蕉网| 亚洲免费在线视频一区 二区| 久久精品色图| 午夜精品久久久| 欧美电影在线播放| 久热精品视频在线免费观看| 欧美性大战久久久久久久| 欧美成人综合在线| 国产视频一区在线观看一区免费| 亚洲欧洲三级电影| 在线播放豆国产99亚洲| 亚洲一区免费| 中文在线资源观看网站视频免费不卡 | 久久国产精品久久精品国产| 国产精品99久久不卡二区| 久久天天躁狠狠躁夜夜爽蜜月| 亚洲欧美国产精品va在线观看 | 开心色5月久久精品| 欧美一区二区观看视频| 欧美日韩精品一区二区| 欧美成人精品不卡视频在线观看| 国产嫩草影院久久久久| 一区二区三区福利| 一区二区三区欧美在线观看| 免费永久网站黄欧美| 久久人人爽人人爽爽久久| 国产乱码精品1区2区3区| 亚洲色诱最新| 亚洲影音一区| 国产精品99一区二区| 日韩视频在线观看一区二区| 99精品免费| 欧美日韩国产天堂| 99在线|亚洲一区二区| 亚洲免费电影在线| 欧美激情视频一区二区三区在线播放| 美女精品视频一区| 在线观看国产成人av片| 久久三级视频| 欧美激情一区在线| 亚洲精选视频在线| 欧美色综合网| 亚洲影视九九影院在线观看| 欧美一区二区三区啪啪| 国产视频在线观看一区| 久久国产精品久久久久久电车| 久久在线免费观看| 亚洲成人在线| 欧美日韩成人激情| 亚洲一区二区三区777| 久久av二区| 在线观看欧美黄色| 欧美日韩福利视频| 亚洲小视频在线观看| 欧美中文在线免费| 国产一区二区三区黄视频| 久久久久久亚洲精品不卡4k岛国| 免费日本视频一区| 一区二区欧美国产| 国产日韩欧美a| 免费看的黄色欧美网站| 99这里只有久久精品视频| 西西裸体人体做爰大胆久久久| 狠狠入ady亚洲精品| 欧美成人精品不卡视频在线观看| 夜夜狂射影院欧美极品| 久久精品国产77777蜜臀| 亚洲国产精品va| 欧美体内she精视频在线观看| 欧美一区二区在线| 亚洲精品三级| 老司机久久99久久精品播放免费| 日韩视频在线免费观看| 国产午夜精品美女视频明星a级| 久久综合综合久久综合| 亚洲免费一在线| 欧美激情成人在线| 欧美一区二区三区成人| 亚洲理论在线| 国内精品久久久| 欧美三区视频| 欧美/亚洲一区| 午夜久久tv| 在线亚洲免费视频| 亚洲国产精品小视频| 久久亚洲一区二区| 午夜精品福利在线观看| 99精品视频免费全部在线| 国内偷自视频区视频综合| 欧美少妇一区| 欧美精品一区二区高清在线观看| 久久激情视频久久| 亚洲一区二区三区视频| 亚洲精品日韩在线观看| 欧美岛国在线观看| 久久亚洲精品一区二区| 欧美亚洲一区三区| 亚洲女人天堂av| 一区二区三区www| 亚洲美女在线看| 亚洲激情成人| 亚洲电影在线观看| 精品动漫一区二区| 国产有码一区二区| 国产亚洲欧美日韩日本| 国产精品入口夜色视频大尺度| 欧美日韩国产在线观看| 欧美黄色免费网站| 欧美国产一区二区三区激情无套| 久久综合色8888| 久久久免费精品视频| 久久国产66| 久久精品中文字幕一区| 欧美在线观看一区二区三区| 午夜精品久久久久久99热| 亚洲免费视频在线观看| 亚洲性线免费观看视频成熟| 亚洲天堂偷拍| 亚洲女人av| 欧美一区二区三区四区在线观看地址| 亚洲欧美视频一区二区三区| 性色av一区二区三区红粉影视| 亚洲欧美变态国产另类| 亚洲欧美电影院| 欧美一区二区三区久久精品 | 亚洲国产免费| 亚洲老司机av| 亚洲性视频网址| 久久高清福利视频| 欧美v亚洲v综合ⅴ国产v| 欧美激情日韩| 国产精品扒开腿做爽爽爽视频| 国产精品亚洲综合久久| 国产一区二区三区高清| 亚洲国产日韩欧美在线99 | 一区二区冒白浆视频| 亚洲欧美日韩系列| 久久综合网色—综合色88| 欧美激情91| 亚洲网站视频福利| 久久久久久久久久久久久9999| 农村妇女精品| 国产精品久久久久一区二区三区| 国产午夜精品久久久久久久| 亚洲欧洲精品一区二区精品久久久| 99视频精品全部免费在线| 欧美一区三区二区在线观看| 欧美国产日韩亚洲一区| 亚洲性视频网址| 欧美大尺度在线观看| 国产欧美精品va在线观看| 亚洲成人在线免费| 亚洲欧美中日韩| 欧美国产精品人人做人人爱| 亚洲视频在线观看| 欧美成人免费网| 国产一区二区日韩精品欧美精品| 日韩网站在线看片你懂的| 久久不射2019中文字幕| 亚洲人成亚洲人成在线观看| 欧美一区二区三区在线视频| 欧美日韩国产影片| 在线观看日产精品| 性娇小13――14欧美| 亚洲精品乱码| 毛片av中文字幕一区二区| 国产乱码精品一区二区三区av| 99亚洲精品| 欧美成人午夜| 久久精品视频在线播放| 国产精品日韩一区| 亚洲欧美国产制服动漫| 亚洲欧洲一区二区在线播放| 久久久精品2019中文字幕神马|