数据结构论坛

首页 » 分类 » 常识 » 基础数据结构数组
TUhjnbcbe - 2021/5/1 22:00:00

思考

面试经典

给你一个文件,里面包含全国人民的年龄数据,现在要你统计每个年龄有多少人?

限定条件:一台机器为单台+2核CPU+2G内存。不得使用现成的容器,比如map等。

文件的存储格式如下,一行一个年龄数据,文件大概5GB。

如果没有上面的限定条件,有很多人会想到分布式,文件有5G数据,一台机器处理不过来,把文件分成小文件,每台机器处理一部分小文件然后汇总。但是这个问题使用分布式,有种杀鸡焉用宰牛刀的感觉,而且造成很多资源的浪费。

分析

全国人民,数据大概有14亿,年龄的范围为0~。

使用排序算法

像这样先排好序,然后统计每一个年龄的个数。但是排序的最高效算法时间复杂度O(nlogn),有14亿的数据,排不出来,而且数据有5GB,内存也不够,所以使用排序算法解决不了这个问题。

使用数组

申请存储空间为的数组,每次读取一行数据,年龄对应数组的下标,每次加加。比如inta[]=newint[];a[18]++,18表示的是18岁的人,a[18]就是表示是18岁有多少个。

代码实现

/***算法题:*给你一个文件,里面包含全国人民的年龄数据,现在要你统计每个年龄有多少人?*限定条件:一台机器为单台+2核CPU+2G内存。不得使用现成的容器,比如map等。*文件的存储格式,一行一个年龄数据,文件大小为5GB。**

authorHowell*

emailhowellhong

.
1
查看完整版本: 基础数据结构数组