C++研究

Ｃ++細(xì)節(jié)深度探索及軟件工程

C++博客 :: 首頁(yè) :: 新隨筆 :: 聯(lián)系 :: 聚合

:: 管理 ::

37 隨筆 :: 0 文章 :: 74 評(píng)論 :: 0 Trackbacks

求有序序列公共部分(集合交集的O(n)復(fù)雜度求法)

#include "stdafx.h"

#include <iostream>

#include <map>

#include <sstream>

using namespace std;

#pragma warning (disable:4305)

typedef map<int, float> FloatMap;

typedef FloatMap::iterator FloatMapIter;

typedef FloatMap::const_iterator FloatMapCIter;

int main()

{

FloatMap _map1, _map2;

_map1[1] = 0.01;

_map1[3] = 0.03;

_map1[4] = 0.04;

_map1[5] = 0.05;

_map1[7] = 0.07;

_map1[101] = 0.101;

_map1[109] = 0.109;

_map2[1] = 0.01;

_map2[4] = 0.04;

_map2[5] = 0.05;

_map2[7] = 0.07;

_map2[101] = 0.101;

_map2[103] = 0.103;

_map2[108] = 0.108;

FloatMapCIter it1 = _map1.begin();

FloatMapCIter it2 = _map2.begin();

FloatMapCIter it22 = _map2.begin();

FloatMapCIter it11 = _map1.begin();

ostringstream os1; //fenzi

ostringstream os11; //fenmu1

ostringstream os22; //fenmu2

//是否有公共部分

int flag = 0;

while(it1 != _map1.end())

{

int id = (*it1).first;

float v1 = (*it1).second;

while( it22 != _map2.end() && (*it22).first < id) ++it22;

if( it22 == _map2.end())

{

break;

}

if( (*it22).first == id )

{

//有公共部分

flag = 1;

os1 << (*it22).first << " "; //fenzi

cout << (*it22).second << "*" << v1 << endl;

it22++;

}

//it2 -- it22

FloatMapCIter itemp = it2;

while( itemp != it22)

{

os22 << (*itemp).first << " " ; //fenmu

++itemp;

}

it2 = it22;

int id2 = (*it2).first;

float v2 = (*it2).second;

while( it11 != _map1.end() && (*it11).first < id2)

{

++it11;

}

if ( it11 == _map1.end())

{

break;

}

if( (*it11).first == id2 )

{

//有公共部分

flag = 1;

os1 << (*it11).first << " "; //fenzi

cout << (*it11).second << "*" << v2 << " ";

it11++;

}

itemp = it1;

while( itemp != it11)

{

os11 << (*itemp).first << " " ; //fenmu

++itemp;

}

it1 = it11;

}//while

//是否有公共部分

if (flag == 1)

{

while( it2 != _map2.end() )

{

os22 << (*it2).first << " " ; //fenmu

++it2;

}

while( it1 != _map1.end() )

{

os11 << (*it1).first << " " ; //fenmu

++it1;

}

else

{

return 0;

}

cout << "Common:" << os1.str() << endl;

cout << "fenmu:" << os11.str() << endl;

cout << "fenmu:" << os22.str() << endl;

system("pause");

return 0;

}

posted on 2008-01-15 21:12 常興龍閱讀(2169) 評(píng)論(1) 編輯收藏引用所屬分類: STL 、Algorithm 、ACM

評(píng)論

# re: 求有序序列公共部分(集合交集的O(n)復(fù)雜度求法) 2014-04-10 15:34 黃智

取交集可不是這么取的吧?一趟循環(huán)即可! 回復(fù) 更多評(píng)論

刷新評(píng)論列表

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！

相關(guān)文章: 求有序序列公共部分(集合交集的O(n)復(fù)雜度求法) 對(duì)包含Struct的Vector就其中的一種屬性排序 [資料]STL種容器的基本使用方法 C++ streams (How to use ostream & istream ?)

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

>　hi的博客

C++研究

公告

常用鏈接

留言簿(8)

隨筆分類(19)

隨筆檔案(37)

相冊(cè)

收藏夾

好友連接

學(xué)術(shù)算法研究

最新隨筆

搜索

積分與排名

最新評(píng)論

閱讀排行榜

評(píng)論排行榜

評(píng)論