华为机考题：合并表记录

题目描述

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

输入描述

先输入键值对的个数n，然后输入成对的index和value值，用空格隔开。

• 1 ≤ n ≤ 500

• 0 ≤ index ≤ 11111111

• 1 ≤ value ≤ 100000

输出描述

输出合并后的键值对（多行），格式为index value，按index升序排列。

示例

输入：

text

4 0 1 0 2 1 3 3 4

输出：

text

0 3 1 3 3 4

说明：索引 0 出现两次，值 1 + 2 = 3；其余索引只出现一次。

C 语言解决方案

思路

由于index最大可达11111111（约一千万），直接用数组当桶会超内存（1000 万 × 4 字节 ≈ 40MB，勉强但偏大）。

更稳妥的做法：

1. 用一个结构体数组存放(index, value)。

2. 按index排序。

3. 遍历排序后的数组，相邻相同index的值累加后输出。

这里使用qsort排序。

代码实现

c

#include <stdio.h> #include <stdlib.h> typedef struct { int index; int value; } Record; // qsort 的比较函数：按 index 升序 int cmp(const void *a, const void *b) { Record *ra = (Record *)a; Record *rb = (Record *)b; if (ra->index != rb->index) { return ra->index - rb->index; } return 0; } int main(void) { int n; scanf("%d", &n); Record recs[505]; for (int i = 0; i < n; i++) { scanf("%d %d", &recs[i].index, &recs[i].value); } // 按 index 升序排序 qsort(recs, n, sizeof(Record), cmp); // 遍历合并相邻相同 index 的记录 for (int i = 0; i < n; ) { int idx = recs[i].index; int sum = 0; int j = i; // 累加所有相同 index 的 value while (j < n && recs[j].index == idx) { sum += recs[j].value; j++; } printf("%d %d\n", idx, sum); i = j; // 跳过已处理的记录 } return 0; }

代码说明

复杂度分析

• 时间复杂度：O(n log n)，主要是排序的开销；合并遍历为 O(n)。

• 空间复杂度：O(n)，存储记录数组。

测试用例