腾讯算法题:服务器内存1G,有一个2G的文件,里面每行存着一个QQ号(5-10位数),怎么最快找出出现过最多次的QQ号。 

解决方案 »

  1.   

    方法一:
    1.在2G文件中找到QQ的最大号与最小号。
    2.采用二分法,以最大号与最小号的中间号,把全部数据分成两个文件存在硬盘上。如果单个文件大于1G,再把这个文件再以中间号分成两个文件。最后保证每个文件都小于1G
    3.因为QQ号都是数字,把每个小于1G的文件中的QQ号,做一次从小到大排序。
    4.分别计算每个文件中的重号记录个数。由于小号不会出现在大号部份,大号在大号部分找,小号在小号部份找,这样查找重号就会很快。
    5.由于每个文件都按QQ号排序,所以找重号时,找到大于本身的号时,就停止查找重号,开始下一次查找重号,这样又一次提高了查找效率。
    方法二:
    1.打开2G文件,一行一行读。
    2.读一行,在硬盘上建一个以该行QQ号为文件名的文件,往该文件写入一个字符(如果该文件已存在,就直接写入一个字符)。
    3.当文件读完后,在生成的文件中,找到文件尺寸最大的那个文件,该文件名就是我们要找的QQ号。
    注:写入的字符应该是相同的,避免因为字符差异造成文件尺寸变化。
    回帖有分加,百度找的、、