本文共 1198 字，大约阅读时间需要 3 分钟。
在面试百度的过程中，有两轮面试都问到了海量数据的问题，对于百度这种在平时业务中就要处理海量数据的公司，问海量数据的处理也情有可原，而且考查海量数据的问题也可以考查到应聘者分析和分解问题的能力。
这种问题是比较常规的海量数据的问题，在剑指offer书中也专门有提到这个问题(专门指出百度喜欢问海量数据问题 哈哈)，海量数据中找前k大的数，可以使用最小堆来解决，具体如下：
选取前k个数构建最小堆，堆顶为当前k个数中最小的数
遍历所有的数字，如果数字比堆顶元素大，则删除堆顶元素，并将大的数字放入堆中
当遍历完所有的数字，堆中就是k个最大的数字
面试官说，这个问题不是为了考查海量数据，而是为了考查分解问题的能力，哈哈。
中位数的概念就是n个数字中，如果从小到大排列，当n是奇数时，中间的数字是中位数，当n是偶数时，中间两个数字的平均是中位数。
寻找中位数可以对数据进行排序，然后直接选中间的数字就可以，排序的时间复杂度是O(nlogn)，但是对于海量数据来说，排序的代价难以承受，因此需要找其他的方法。排序中比较喜欢用快排，快排的思想是选取标兵，然后将数据以标兵为界，小于标兵的放左边，大于标兵的放右边，那换个思路，海量数据中，选取一个标兵，然后将小于他的数据放在一个文件中，大于他的数据放另一个文件中，同时对两个问题的数据量进行统计，如果两个文件中的数据量相同，那么这个标兵就是中位数，如果小的文件多，则在小文件中继续选取标兵，这个Partition的思想就可以通过二分解决海量数据中找中位数的问题。所以面试官说这是在考查分解问题的能力也没有问题。
嗯，简单些的问题，哈哈，我信。
由上可知，海量数据不能全部拉到内存中进行排序，内存放不下，因此解决思路还是分解问题，将一个文件中的数分成两个或多个文件，如果文件还是大，继续分。
这个问题可以用哈希的思想，如每行的数有一串单个0-9的数字组成，那么可以通过给每个数最后一位进行划分，最后一位为0的放一个文件，为1 的放一个文件，经过一轮，将一个大文件分解为十个小文件，如果十个小文件依旧比较大，则可以继续以倒数第二位进行划分，或者直接以后两位直接划分，可以分为100个文件。这个分解，最终会得到可以直接进行统计的小文件，统计每个小文件中重复次数最多的数字，多个小文件之间进行比较，最终可以得到重复次数最多的数字。
无论是paitition还是hash ，确实是在分解海量数据，考查分解问题的能力，无可厚非。
转载地址：http://sqhzb.baihongyu.com/