输入:给定n个元素的数组,其中包含从0到n-1的元素,这些数字中的任何一个都会出现任意次数.
目标:在O(n)中找到这些重复数字并仅使用常量存储空间.
例如,设n为7,数组为{1,2,3,1,3,0,6},答案应为1和3.我在这里检查了类似的问题,但答案使用了一些数据结构等HashSet.
任何有效的算法都相同？
我这里有一个非常奇怪的案例.我有一个包含数百万条目的文件,并想知道是否存在至少一个重复项.这里的语言不是很重要,但C似乎是速度的合理选择.现在,我想知道的是采取什么样的方法？速度是这里的主要目标.当然,我们希望一旦找到一个副本就停止查看,这很清楚,但是当数据进入时,我不知道它是如何排序的.我只知道它是一个字符串文件,由换行符分隔.现在请记住,我想知道的是,是否存在重复.现在,我发现了许多关于在数组中查找所有重复项的问题,但是大多数问题都是简单而全面的,而不是最快的.
因此,我想知道:找出一个数组是否包含至少一个副本的最快方法是什么？到目前为止,我能在SO上找到的最接近的是:找出数组中的重复元素.选择的语言并不重要,但是因为它毕竟是编程,所以多线程是可能的(我只是不确定这是否是一种可行的方法).
最后,字符串的格式为XXXNNN(3个字符和3个整数).
请注意,这不是严格的理论.这将一台机器(英特尔i7处理器搭配8GB RAM)上进行测试,所以我必须考虑让字符串比较等等.这就是为什么我也想知道,如果它可能是时间快于分割字符串二,首先比较整数部分,因为int比较会更快,然后是字符串部分？当然,这也需要我拆分字符串并将后半部分转换为int,这可能会更慢......