题解 | #合并表记录#

合并表记录

http://www.nowcoder.com/practice/de044e89123f4a7482bd2b214a685201

合并表记录

描述

数据表记录包含表索引和数值（int范围的正整数），请对表索引相同的记录进行合并，即将相同索引的数值进行求和运算，输出按照key值升序进行输出。
示例

输入：

4
0 1
0 2
1 2
3 4

输出：

0 3
1 2
3 4

方法一

思路分析

本题方法一使用暴力求解，即：先将所有的索引和数值全部存储起来，然后两层循环找到重复的索引数值合并，并对重复的结点进行标记，最后顺序输出所有的索引数值。具体实现如下：

设置一个结构体，含有索引和数值，此外还设置了一个标记，用于表示是否重复；
然后循环将重复的索引的数值求和，并标记重复索引数值对（除第一个）
根据index对所有的索引数值进行排序
最后顺序输出非重复的索引数值

图解

$index$	0	0	1	3	1
$value$	1	2	2	4	1
$index_i$	1	1	1	1	1

(1)两重循环合并重复的索引数值对，并将重复的索引数值标记，如下：

$index$	0	0	1	3	1
$value$	3	2	3	4	1
$index_i$	1	-1	1	1	-1

(2)随后按照$index$进行排序，得到：

index	0	0	1	1	3
value	3	2	3	1	4
$index_i$	1	-1	1	-1	1

(3)输出$index_i=1$的索引数值对。

核心代码

#include<bits/stdc++.h>
using namespace std;
struct table
{
    int index;
    int value;
    int index_i=1;//标记这组数是否重复，1表示不重复
};
bool Cmpare(const table &a, const table &b)
{
     return a.index < b.index;//按照index排序
}
int main()
{
    int n;
    cin>>n;
    vector<table>temp(n);
    for(int i=0;i<n;i++)
    {
        int m,p;
        cin>>m>>p;
        temp[i].index=m;
        temp[i].value=p;
    }
     for(int i=0;i<n;i++)
    {
       for(int j=i+1;j<n;j++)
       {
           if(temp[j].index_i!=-1&&temp[i].index==temp[j].index)//将重复的结点合并，并标记
           {
               temp[i].value+=temp[j].value;
               temp[j].index_i=-1;
           }
       }
    }
    sort(temp.begin(),temp.end(),Cmpare);//按照index排序
    for(int i=0;i<n;i++)
    {
        if(temp[i].index_i==1)//输出不重复的结点
           cout<<temp[i].index<<" "<<temp[i].value<<endl;
    }
    
    return 0;
}

复杂度分析

时间复杂度：二重循环对所有的重复索引数值合并，时间复杂度为$O(n^2)$，按照索引值对索引数值排序，时间复杂度为$O(nlogn)$，因此总的时间复杂度为$O(n^2)$
空间复杂度：设置结构体数组存储所有的索引数值，在结构体中有必要的int值存储索引数值，还设置了一个标记整数，因此需要额外的内存空间，因此空间复杂度为$O(n)$

方法二

思路分析

直接使用C++中STL中的map结构。C++ 中 map 提供的是一种键值对容器，里面的数据都是成对出现的，每一对中的第一个值称之为关键字(key)，每个关键字只能在 map 中出现一次；第二个称之为该关键字的对应值。

核心代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    map<int,int> mp;//初始化map,value=0
    for(int i=0;i<n;i++)
    {
        int p=0,q=0;
        cin>>p>>q;
        mp[p]+=q;//合并重复的点
    }
    for(auto it = mp.begin();it!=mp.end();++it)
        cout<<it->first<<" "<<it->second<<endl;
    
}

复杂度分析