首页 > 试题广场 > 合并表记录
[编程题]合并表记录

数据表记录包含表索引和数值,请对表索引相同的记录进行合并,即将相同索引的数值进行求和运算,输出按照key值升序进行输出。


输入描述:

先输入键值对的个数
然后输入成对的index和value值,以空格隔开



输出描述:

输出合并后的键值对(多行)

示例1

输入

4
0 1
0 2
1 2
3 4

输出

0 3
1 2
3 4

python解法,使用defaultdict,非常适合这道题:

from collections import defaultdict
while True:
    try:

        a,dd=int(input()),defaultdict(int)
        for i in range(a):
            key,val=map(int,input().split())
            dd[key]+=val
        for i in sorted(dd.keys()):
            print(str(i)+" "+str(dd[i]))


    except:
        break
发表于 2017-10-04 15:07:50 回复(11)
//C++ //C++,用stl中的map
#include<iostream>
#include<map>
using namespace std;

int main()
{
    int n;
    while(cin >> n){
        map<int,int> m;
        while(n--){
            int key,value;
            cin >> key >> value;
            if(!m[key]){
                m[key] = value;
            }
            else m[key] += value;//不存在时赋值,存在时累加
        }
		//map内部本身就是按照key的大小顺序进行存储的 
		for(map<int,int>::iterator it=m.begin();it!=m.end();++it){
            cout << it->first << " "<< it->second << endl;
        }
    }
    return 0;
} 


发表于 2016-04-22 10:58:02 回复(13)
#include <iostream>
#include <map>
using namespace std;
int main()
{
	map<int, int> iimap;
	int key, value, num;
	cin >> num;
	while (num-- && cin >> key >> value)
		iimap[key] += value; //不存在的时候默认是0,存在则累加
	for (auto beg = iimap.begin(); beg != iimap.end(); ++beg)
		cout << beg->first << " " << beg->second << endl;
	return 0;		
}

发表于 2016-07-12 15:52:56 回复(2)
这道题的方法有很多种,其中最关键的一点是数据结构,也就是说你打算用什么样的方式来存放表每一项的索引和键值,最容易想到的一种方法是使用结构体,这个结构体包含两项分别为索引和键值,于是整个表就是这样的一个结构体数组,这种方法很常规,但是其实有一个更为简单的小技巧,我们不需要去定义结构体,只使用普通的数组就可以完成,我们需要处理的数据有两项,一项是index索引,一项是键值value,我们可以把index用数组下标来存放,而键值用数组元素的值来存放,这样我们存放的数据在数组中是不连续的,但是不论是代码还是思路都会大大简化,代码如下
 #include<iostream>
 using namespace std;
 int  main()
 {
  int Key_Value[10000]={0},Key,Value,Number,i;
  cin>>Number;
  for(i=0;i<Number;i++)
  {
   cin>>Key>>Value;
   Key_Value[Key]+=Value;
  }
  for(i=0;i<10000;i++)
  {
   if(Key_Value[i]!=0)
    cout<<i<<"  "<<Key_Value[i]<<endl;
  }
  return 0;
 }
//以上的这种方法虽然比较简单,但是中间有一个小Bug,在这里虽然可以通过所有测试,但是必须是在相同索引项最后的键值和不为0的情况下才能正确,而这里牛客的测试数据最后的输出结果的键值都是非0值,所以也通过了,但是更严谨地来应该采用一种更为常规的方法,也就是用结构体来设计算法,这样输入的每一项是一种连续存放的数据结构,相对第一种方法来说代码更复杂一点,但是更具有普适性,代码如下
#include<iostream>
using namespace std;
struct Key_Value_Pair
{
	int index;
	int value;
};
int main()
{
	Key_Value_Pair Part[1000];
	int Key_Value_Pairs_Num,i,j,k;
	cin>>Key_Value_Pairs_Num;
	for(i=0;i<Key_Value_Pairs_Num;i++)
		cin>>Part[i].index>>Part[i].value;
	for(i=0;i<Key_Value_Pairs_Num;i++)
	{
		for(j=i+1;j<Key_Value_Pairs_Num;j++)
		{
			if(Part[i].index==Part[j].index)
			{
				Part[i].value+=Part[j].value;//对第二键值求和,累加在第一次出现的键值项上,下一步进行重复索引的删除操作
				for(k=j;k<Key_Value_Pairs_Num-1;k++)
					Part[k]=Part[k+1];
				j--;
				Key_Value_Pairs_Num--;
			}
		}
	}
	//下面进行排序操作
	Key_Value_Pair Temp;//定义一个结构体,作为交换操作的中间值
	for(i=0;i<Key_Value_Pairs_Num-1;i++)
	{
		for(j=0;j<Key_Value_Pairs_Num-1-i;j++)
		{
			if(Part[j].index>Part[j+1].index)
			{
				Temp=Part[j];
				Part[j]=Part[j+1];
				Part[j+1]=Temp;
			}
		}
	}
	for(i=0;i<Key_Value_Pairs_Num;i++)
		cout<<Part[i].index<<" "<<Part[i].value<<endl;
	return 0;
} 


编辑于 2016-03-14 19:27:07 回复(30)

import java.util.Iterator;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			Map<Integer, Integer> map = new TreeMap<Integer, Integer>();
			int n = sc.nextInt();
			for (int i = 0; i < n; i++) {
				int s=sc.nextInt();
				int value=sc.nextInt();
				if (map.containsKey(s)) {
					map.put(s, map.get(s) + value);
				} else
					map.put(s, value);
			}
			for (Integer key : map.keySet()) {
				System.out.println(key + " " + map.get(key));
			}
		}
	}
}


发表于 2016-03-26 22:05:44 回复(14)
我还是比较喜欢STL中的map
学会STL  走遍天下全都会
#include <iostream>
#include <map>

using namespace std;

int main()
{
	//map<int, int> union_table;//one 若定义在while外边,即使用多次,需要clear
	int count;
	int index, value;
	while (cin >> count)
	{
        map<int, int> union_table;//two
		while (cin >> index >> value)
		{
			if (union_table.find(index) != union_table.end())
				union_table[index] += value;
			else
				union_table.insert(make_pair(index, value));
			count--;
			if (count == 0) break;
		}
		for (auto it = union_table.begin(); it != union_table.end(); it++)
		{
			cout << it->first << " " << it->second << endl;
		}
		//union_table.clear();//one
	}


	//system("pause");
	return 0;
}

发表于 2016-07-04 23:57:59 回复(3)
C 语言版的: 
#include<stdio.h>
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
int temp,i,j,a[1024],b[1024];
        for(i=0;i<n;i++){
            scanf("%d%d",&a[i],&b[i]);
        }
        for(i=0;i<n-1;i++){
            for(j=i+1;j<n;j++){
                if(a[i]>a[j]){
                temp=a[i],a[i]=a[j],a[j]=temp;
                temp=b[i],b[i]=b[j],b[j]=temp;
            }
            }
        }
      for(i=0;i<n;i++)
          {
 while(i<n-1&&a[i]==a[i+1]){
 b[i+1]=b[i]+b[i+1];
 i++;
 }
          printf("%d %d\n",a[i],b[i]);    
      }
    }
}
发表于 2016-09-05 13:04:46 回复(0)
import java.util.TreeMap;
import java.util.Scanner;

public class Main{
    
    public static void main(String[] args){
        
        Scanner sc=new Scanner(System.in);
        TreeMap<Integer,Integer> map=new TreeMap<Integer,Integer>();
            
            
        int size=sc.nextInt();
        
        while(sc.hasNext()){
            
            int key=sc.nextInt();
            int val=sc.nextInt();
            
            if(map.containsKey(key)){
                
                map.put(key,val+map.get(key));
                

                
            }else{
                
                map.put(key,val);
                
                
            }

        }

        
        for(int key:map.keySet()){
            
            System.out.println(key+" "+map.get(key));
            
        }
    }

}
发表于 2017-06-22 11:35:33 回复(6)
Python:因为有key值和value值就想着用字典 ,但是字典的输出是无序的,因此有个函数sorted可以对key值排序,然后按照这个顺序输出字典 的value
num=int(input())
dict={}
for i in range(num):
    m, n = map(int, input().split())
    if dict. __contains__(m):
        dict[m]+=n
    else:
        dict[m]=n
dic= sorted(dict.keys())
for i in dic:
    print(i,dict[i])

发表于 2017-11-28 10:54:50 回复(2)
#include<map>
#include<iostream>
using namespace std;
int main(){
    int num= 0;
    cin>>num;
    map<int, int> mInput;
    int index= 0, value= 0;
    for(int i= 0; i < num; ++i){
        cin>>index>>value;
        mInput[index] += value;
    }
    for(auto iter= mInput.begin(); iter != mInput.end(); ++iter){
        cout<<iter->first<<" "<<iter->second<<endl;
    }
    return 0;
}
//如果你了解map,代码其实很简洁

发表于 2017-06-10 20:55:30 回复(0)
nodejs处理方法。
由于node的输入的方式很特殊。
所以采用的是 全局输入arr 
分别对 输入的字符串 分割成 index 和 value push到 数组中,
再对index 和 value处理。
最后把index 和 value的对应元素组成 对象数组排序就可
var rl = require('readline').createInterface(process.stdin,process.stdout);
var arr = [];
var index=[];
var value =[];
rl.on('line',function(data){
    arr.push(data);
    var n = arr[0]-0;
    if(arr.length == n+1){
        index = arr.slice(1).map(function(i){
            var ind = i.split(" ").slice(0,1)-0;
            return ind;
        });

        value = arr.slice(1).map(function(i){
            var val = i.split(" ").slice(1)-0;
            return val;
        });

        for(var i = 0;i<index.length;i++){
            for(var j = i+1;j<index.length;){
                if(index[i] == index[j]){
                    value[i] += value[j];
                    index.splice(j,1);
                    value.splice(j,1);
                }else{
                  j++;
                }
            }
        }
        var k = 0;
        var objarr = [];
        while(k<index.length){
            objarr.push({index:index[k],value:value[k]});
            k++;
        }
        
        objarr.sort(function(a,b){return a.index - b.index;});
        for(var k = 0;k<objarr.length;k++){
            var ele = objarr[k];
            console.log(ele.index+" "+ele.value);
        }
        arr = [];

    }
})

发表于 2016-08-04 17:08:13 回复(7)
#include <stdio.h>
#include <string.h>
int main()
{
    int i, n, tmp1, tmp2;
    scanf("%d", &n);
    int arr[1000];
    memset(arr, 0, sizeof(arr));
    while(n > 0)
    {
        n--;
        scanf("%d %d", &tmp1, &tmp2);
        arr[tmp1] += tmp2;
    }
    for(i = 0; i < 1000; ++i)
        if(arr[i] > 0)
            printf("%d %d\n", i, arr[i]);
    return 0;
}
用什么数据结构,多累,直接用个数组保存下来输出就好了嘛
发表于 2016-07-11 22:40:53 回复(9)
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.Scanner;

public class Main {

	@SuppressWarnings("resource")
	public static void main(String[] args) {

		/*
		 * 首先建立二维数组,保存所有的数据
		 */
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();// 一共有多少组数字
		int[][] myArray = new int[n][2];// 建立二维数组
		HashSet<Integer> hashSet = new HashSet<>();
		for (int i = 0; i < n; i++) {
			myArray[i][0] = in.nextInt();
			myArray[i][1] = in.nextInt();
			hashSet.add(myArray[i][0]);// 添加进入hashset并进行排序
		}

		for (Integer integer : hashSet) {
			int sum = 0;
			for (int i = 0; i < n; i++) {
				if (integer == myArray[i][0]) {
					sum += myArray[i][1];
				}
			}
			System.out.println(integer + " " + sum);
		}
	}
}
//单机测试通过,不能AC

发表于 2017-06-29 21:44:56 回复(0)
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        // TreeMap中键值会自动按照升序排列
        Map<Integer,Integer> map = new TreeMap<Integer,Integer>();
        while(num>0){
            Integer keyIn = sc.nextInt();
            //如果map中包含有key值,则更新此key值对用的value值;否则不更新,直接将此key-value
            //put进map中;
            if(map.containsKey(keyIn)){
                Integer val = map.get(keyIn)+sc.nextInt();
                map.put(keyIn,val);
            }else{
                map.put(keyIn,sc.nextInt());
            }
            //控制循环结束
            num--;
        }
        //使用Iterator遍历Map
        Iterator iterator = map.entrySet().iterator();
        while(iterator.hasNext()){
            Map.Entry<Integer,Integer> en =(Map.Entry<Integer,Integer>)iterator.next();
            Integer key = en.getKey();
            Integer val = en.getValue();
            System.out.println(key+" "+val);
        }
    }
}

发表于 2017-06-20 11:27:14 回复(0)
#include<iostream>
#include<vector>
 
using namespace std;
 
int main()
    {
    int n;
    int index;
    int value;
    while(cin>>n)
        {
        vector<int> v(n,0);
        for(int i=0;i<n;i++)
            {
            cin>>index>>value;
            if(v[index]==0)            
                v[index]=value;
            else
                v[index]=v[index]+value;
        }
        for(int j=0;j<n;j++)
            {
            if(v[j]>0)
                cout<<j<<' '<<v[j]<<endl;
        }
        
    }
    return 0;
}

发表于 2016-08-18 20:18:21 回复(1)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool compare(pair<int,int> i,pair<int,int> j){
 return i.first<j.first;
}
int main(){
    vector<pair<int,int>> Indix;
    int n;
    cin>>n;
    while(n--){
        int a,b;
        cin>>a>>b;
        Indix.push_back(make_pair(a,b));
        for(int i=0;i<Indix.size()-1;i++){
            if(Indix[i].first==a) {
                Indix[i].second+=b;
                Indix.pop_back();
                break;
            }
        }
    }
    stable_sort(Indix.begin(),Indix.end(),compare);
    for(int i=0;i<Indix.size();i++)
        cout<<Indix[i].first<<" "<<Indix[i].second<<endl;
    return 0;
}
发表于 2017-08-19 18:13:17 回复(1)

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<functional>
#include <map>

using namespace std;

int main()
{
int n;
cin >> n;
map<int, int> count;
int key, value;
for (int i = 0; i < n; ++i)
{
cin >> key >> value;
count[key] += value;
}

for (auto& pr : count)
{
cout << pr.first << " " << pr.second << endl;
}

return 0;
}
发表于 2017-07-04 13:49:01 回复(0)
#include <stdio.h>

#define SIZE 10000

int main(void) {
    int a = 0, b = 0;
    int n = 0, i = 0;
    int sum = 0;
    int arr[SIZE] = {0};
    
    while (scanf("%d", &n) != EOF) {
        for (i = 0; i < n; i++) {
            if (scanf("%d%d", &a, &b) != EOF) {
                arr[a] += b;
            }
        }
        for (i = 0; i < n; i++)
            if (arr[i] != 0)
                printf("%d %d\n", i, arr[i]);
    }
    
    return 0;
}

发表于 2017-07-04 10:41:38 回复(0)
//哈希表
#include<iostream>

using namespace std;
 
int main() 
 {
    const int N=10000;
    long long  hashTab[N];
    for(int i=0;i<N;++i)
        hashTab[i]=0;
    
    int group;
    while(cin>>group)
        {
        for(int i=0;i<group;++i)
            {
            int Index,Value;
            cin>>Index>>Value;
            hashTab[Index] += Value;
        	}
        for(int i=0;i<N;++i)
            {
            if(hashTab[i]>0)
                cout<<i<<" "<<hashTab[i]<<endl;
            
        	}
    }
    
    
    return 0;
    
}

编辑于 2016-08-30 22:15:24 回复(1)
看到key,value,自然想到map,unordered_map,看到排序输出,自然想到使用map,接下来就很简单了。首先在map进行查找,如果没有则插入。如果有就在原来的基础上value相加。最后遍历一下map元素,注意first,second分别表示第一第二元素哈。
#include <iostream>
#include <map>

using namespace std;

int main() {
    int N;
    while (cin >> N) {
        int index, value;
        map<int, int> merge;
        for (int i = 0; i < N; ++i) {
            cin >> index >> value;
            if (merge.find(index) == merge.end()) {
                merge[index] = value;
            } else {
                merge[index] += value;
            }
        }
        
        for (auto it : merge) {
            cout << it.first << ' ' << it.second << endl;
        }
    }
}


发表于 2019-08-17 09:40:13 回复(0)