[面试题][急等]大文件重复行有关问题

[面试题][急等]大文件重复行问题
有一个文件长度大如16G的文件，每行都是16个大写字母组成的乱序字符串，总共有多少行不知道，文件内容太大不能全部读入内存，只能一次读入一部分，要判断文件中哪些行是一样的，输出重复的行是哪些。
这个问题有些东西是我们能看得清楚的：
1、必须用O(N)的时间长度去顺序读取文件。
2、不能用O(N)的空间的内存，不论是文件数据、哈希表、哈夫曼编码，还是平衡二叉树。
3、不能修改文件、创建文件。
4、存在一种简单的方法，双重循环，O(N2)，但是人家希望找到更好的方法。


------解决方案--------------------
16个大写字母组成的乱序字符串 = 2^(4*26) 用bit存状态, 2^(4*26)/8 = 2^26 byte, 即64M。
用自然顺序，每读取一个，如果对应位置没有改变，则改变对应位置的bit状态，否则重复，输出之。


------解决方案--------------------
2、不能用O(N)的空间的内存，
不论是文件数据、哈希表、哈夫曼编码，还是平衡二叉树。

问一下：这个意思说树就不能用了。对了大内存的数据结构 大于o(n)可以吗

4、存在一种简单的方法，双重循环，O(N2)，但是人家希望找到更好的方法。
问一下：能解释下，何种双重循环？
------解决方案--------------------

探讨

16个大写字母组成的乱序字符串 = 2^(4*26) 用bit存状态, 2^(4*26)/8 = 2^26 byte, 即64M。
用自然顺序，每读取一个，如果对应位置没有改变，则改变对应位置的bit状态，否则重复，输出之。

------解决方案--------------------
排序分治啊
分到能装进内存为止。
------解决方案--------------------
按开头字母分到16个文件中
------解决方案--------------------
26^16这么大。安心hash了。