C++研究
C++细节深度探索及软件工程
C++博客
::
首页
::
新随笔
::
联系
::
聚合
::
管理
::
37 随笔 :: 0 文章 :: 74 评论 :: 0 Trackbacks
<
2008年1月
>
日
一
二
三
四
五
六
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
6
7
8
9
公告
致力于百度无线搜索研发。
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
(8)
给我留言
查看公开留言
查看私人留言
随笔分类
(19)
ACM(1)
(rss)
Algorithm(4)
(rss)
Design Patterns & Engeering(4)
(rss)
STL(4)
(rss)
小技巧(6)
(rss)
随笔档案
(37)
2010年3月 (1)
2009年8月 (1)
2009年3月 (1)
2008年10月 (1)
2008年3月 (1)
2008年2月 (2)
2008年1月 (3)
2007年12月 (2)
2007年9月 (4)
2007年7月 (2)
2007年6月 (6)
2007年5月 (2)
2007年4月 (11)
相册
深爱着的母校-天津大学
收藏夹
Goodies
(rss)
好友连接
丑石
(rss)
赵博的Blog连接
学术算法研究
最新随笔
1. [征集]如果百度无线搜索计划产出新产品,你最希望是什么?
2. 百度阿拉丁指亮暗网,何为暗网?
3. 关于http://wap.baidu.com招唤
4. 转入Apache2开发,淡忘windows了
5. VC的Dialog或FormView中的控件不能刷新
6. 关闭Linux下终端或Vi的BEEP声
7. unbuntu Linux下切换GDM与KDM
8. 求有序序列公共部分(集合交集的O(n)复杂度求法)
9. 对包含Struct的Vector就其中的一种属性排序
10. B树ReadKey关键点的操作与实现
搜索
积分与排名
积分 - 69317
排名 - 329
最新评论
1. re: 求有序序列公共部分(集合交集的O(n)复杂度求法)
取交集可不是这么取的吧?一趟循环即可!
--黄智
2. re: Mysql++使用手册及用法规范[未登录]
好东西
--乐乐
3. re: Mysql++使用手册及用法规范
好东西,值得鼓励
--njf
4. re: Mysql++使用手册及用法规范
必然顶楼主!!!!!!!
--扩大客户缴费
5. re: Mysql++使用手册及用法规范
谢了~ 瞅瞅先!
--kongkong
阅读排行榜
1. 有关 C++ 嵌套类 (7782)
2. 关于http://wap.baidu.com招唤(6981)
3. C++ streams (How to use ostream & istream ?)(6853)
4. Mysql++使用手册及用法规范(6510)
5. VC的Dialog或FormView中的控件不能刷新(3067)
6. [资料]STL种容器的基本使用方法(2691)
7. string 类的使用方法(2557)
8. 精炼循环右移(2478)
9. 求有序序列公共部分(集合交集的O(n)复杂度求法)(2140)
10. 对包含Struct的Vector就其中的一种属性排序(2119)
评论排行榜
1. Mysql++使用手册及用法规范(25)
2. Some algorithms about judging a prime .(8)
3. 精炼循环右移(6)
4. Implement "GOF's Adapter pattern" Using C++(Series of Gof patterns using C++ 2nd article) (4)
5. Implement "GOF's Builder pattern" Using C++(Series of Gof patterns using C++ 4th article) (4)
6. [征集]如果百度无线搜索计划产出新产品,你最希望是什么?(4)
7. 关于http://wap.baidu.com招唤(3)
8. 有关 C++ 嵌套类 (3)
9. C++ streams (How to use ostream & istream ?)(3)
10. Something problem resovled [Winsock2&mysql++-2.2.3 Sdk compatible problem](2)
求有序序列公共部分(集合交集的O(n)复杂度求法)
#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
常兴龙
阅读(2140)
评论(1)
编辑
收藏
引用
所属分类:
STL
、
Algorithm
、
ACM
评论
#
re: 求有序序列公共部分(集合交集的O(n)复杂度求法)
2014-04-10 15:34
黄智
取交集可不是这么取的吧?一趟循环即可!
回复
更多评论
刷新评论列表
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
相关文章:
求有序序列公共部分(集合交集的O(n)复杂度求法)
对包含Struct的Vector就其中的一种属性排序
[资料]STL种容器的基本使用方法
C++ streams (How to use ostream & istream ?)
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
Powered by:
C++博客
Copyright © 常兴龙
>
hi的博客