题解 | #合并表记录#

合并表记录

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

#include <stdio.h>

/*int main() {
    int hash[11111112]={};
    int n;
    scanf("%d",&n);
    while(n--){
        int index,val;
        scanf("%d %d",&index,&val);
        hash[index]+=val;
    }
    for(int i=0;i<11111112;i++){
        if(hash[i]!=0){
            printf("%d %d\n",i,hash[i]);
        }
    }

    return 0;
}*/
//上述代码导致内存超限,也就是说直接哈希会出问题
int main(){
    int n;
    scanf("%d\n",&n);
    int record[500][2]={};//用来接收输入的值,因为不能保证
    //输入的值是按照index递增的方式进行的,所以没办法直接在线处理
    for(int i=0;i<n;i++){
        scanf("%d %d\n",&record[i][0],&record[i][1]);
    }
    //接下来对record中的值进行排序,从小到大按照index排序;
    for(int i=0;i<n;i++){
        int min = record[i][0];
        int minIndex = i;
        int j;
        for(j=i+1;j<n;j++){
            if(record[j][0]<min){
                min = record[j][0];
                minIndex = j;
            }
        }
        int tmp = record[i][0];
        int tmp1 = record[i][1];
        record[i][0]=record[minIndex][0];
        record[i][1]=record[minIndex][1];
        record[minIndex][0]=tmp;
        record[minIndex][1]=tmp1;
    }
    //下面对已经排好序的数据进行合并和输出,直接处理
    int tmpIndex = record[0][0];
    int tmpValue = record[0][1];
    for(int i=1;i<n;i++){
        if(record[i][0]==tmpIndex){
            tmpValue+=record[i][1];
        }
        else{
            printf("%d %d\n",tmpIndex,tmpValue);
            tmpIndex = record[i][0];
            tmpValue = record[i][1];
        }
    }
    printf("%d %d\n",tmpIndex,tmpValue);
    return 0;
}

本题最开始的解题思路是直接hash,发现超过了内存限制,于是采用第二种解法

存储index-value对,根据index值按照非递减序列排序,再采用在线处理的方式进行合并输出,总体时间复杂度为排序的时间复杂度,此处为O(n^2),采用其他更高效的排序算法可以达到O(nlogn)的程度。

全部评论

相关推荐

这算盘打的
程序员小白条:都这样的,都是潜规则,你自己说可以实习一年就行了,实习可以随便跑路的
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
昨天 11:29
点赞 评论 收藏
分享
那一天的Java_J...:他本来公司就是做这个的,不就是正常的游戏客户端和服务器开发,软硬件联动,有啥恶心不恶心的,提前告诉你就是怕你接受不了,接受不了就没必要再往后走流程浪费时间,虽然这公司是一坨。
点赞 评论 收藏
分享
06-10 21:15
门头沟学院 Java
宁阿:好多这种没🧠的公司,他们估计都不知道毕业的人不能给安排实习岗
实习吐槽大会
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务