C++研究

Ｃ++细节深度探索及软件工程
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  37 随笔 :: 0 文章 :: 74 评论 :: 0 Trackbacks
求有序序列公共部分(集合交集的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 常兴龙 阅读(2148) 评论(1)  编辑 收藏 引用 所属分类: STL 、Algorithm 、ACM

评论

# re: 求有序序列公共部分(集合交集的O(n)复杂度求法) 2014-04-10 15:34 黄智
取交集可不是这么取的吧?一趟循环即可!  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


>　hi的博客