file-io - O(c) 读取几个演出文本文件的时间复杂度

Question

我的任务是解决如下难题：编写一个输入解析器（用 C、Python、Java 或 Go 语言），它从标准输入读取文件并将数据读入字节数组（8 位字节）。检查该行是否具有一组唯一的字节值。如果是这样，它应该跟踪行号最后，它应该打印出在每一行上具有唯一一组字节值的行号。

- 程序应该以高效的方式和时间运行——它不应该达到很大的 O(n^2) 复杂度或更糟。试着看看你是否能在大 O(n) 时间内做到这一点。- 文件应该被读入一个字节数组（8 位值）而不超出内存。

我正在读取我正在使用的示例文件，它是 50MBfile ，逐行并将行存储在一个字节数组中，然后调用一个方法checkDuplicate(byte[] arr)并传递字节数组，然后创建一个哈希集并循环遍历数组的元素和将它们添加到哈希集，然后返回哈希集的大小。由于哈希集不允许重复返回主我检查返回的大小是否等于数组大小以确定它是否是唯一的或不保存行号。

private  int checkDuplicate(byte[] arr) {
         HashSet<Byte> byteSet = new HashSet<Byte>();
         int size=0;
         for (byte e : arr){

                if (e != 0 && byteSet.add(e)) {}

                    size = byteSet.size();
            }

        return size;
    }

可以实现 O(c) 或 O(n) 吗？到目前为止我得到了 O(n^2) 并且稍后当我达到 O(n) 时将处理内存异常。

另外，用python解决问题会降低时间/空间复杂度吗？

标签： file-iotime-complexityspace-complexity