相关疑难解决方法(0)

找到在列表中只出现一次的数字的最佳算法是什么,其中所有其他数字恰好发生两次.

因此,在整数列表中(让它作为一个数组),每个整数重复两次,除了一个.找到那个,什么是最好的算法.

与经典问题相关的是找到一个不在40亿个给定值中但不完全相同的整数.

为了澄清,通过整数我真正的意思只是其数学定义的一个子集.也就是说,假设只有有限数量的整数.用C++说,它们int在范围内[INT_MIN, INT_MAX].

现在给出一个std::vector<int>(没有重复)或者std::unordered_set<int>其大小可以是40,400,4000左右,但不是太大,如何有效地生成一个保证不属于给定数字的数字？

如果不担心溢出,那么我可以将所有非零的相加,并将产品加1.但是有.对手测试用例可以包含INT_MAX.

我更赞成简单,非随机的方法.有没有？

谢谢!

更新:为了消除歧义,让我们说一个未分类的std::vector<int>,保证没有重复.所以我问是否有比O(n log(n))更好的东西.另请注意,测试用例可能包含INT_MIN和INT_MAX.

这是一个面试问题:

有10亿个手机号码有11个数字,它们随机存储在一个文件中,例如12345678910,第一个数字必须是1.通过这些数字查看是否有一个有重复的数字,只看看是否存在重复,如果找到重复,则返回True,或返回False. 只允许10 MB内存.

这是我的解决方案:

将所有这些数字哈希分成1000个文件hash(num)%1000,然后重复项应该归入同一个文件.

散列后,我得到了1000个小文件,每个文件都包含1 million数字at most,对吧？我不确定这一点,我只是这样做1 billion / 1000 = 1 million.

然后,对于每个文件,构建一个哈希表来存储每个数字,并flag表示其出现次数.

我想,它需要5 B代表数字,4 B低位8 digits和1 B高位3 digits; 并且实际上1 bit就足够了flag,因为我只需要找出重复是否存在,只需要多少次.但是,我如何将1 bit标志应用于每个数字？我跌跌撞撞,所以我选择bool成为旗帜,1 B被带走.最后,哈希表中的每个数字都将采用5B<for number> + 1B<for flag> + 4B<for the next-pointer> = 10B,然后每个文件将采用10M哈希表.

那是我愚蠢的解决方案,请给我一个更好的解决方案.

谢谢.

跟进:

如果有no duplicates这10亿个电话号码,给定一个电话号码,如何查找给定的is or is …

问题是,给定一个包含40亿个整数的输入文件,提供一个算法来生成一个未包含在文件中的整数,假设只有10 MB的内存.

搜索了一些解决方案,其中之一是将整数存储到位向量块(每个块表示40亿范围内的特定整数范围,块中的每个位表示整数),并为每个块使用另一个计数器,计算每个块中的整数数.因此,如果整数的数量小于整数的块容量,则扫描块的位向量以找到缺少的整数.

我对此解决方案的困惑是,当块计数器阵列占用与位向量相同的存储器时,提到最佳最小占用空间.我很困惑为什么在这种情况下它是最佳的最小足迹？

这是我提到的计算细节,

Let N = 2^32.
counters (bytes): blocks * 4
bit vector (bytes): (N / blocks) / 8
blocks * 4 = (N / blocks) / 8
blocks^2 = N / 32
blocks = sqrt(N/2)/4

林先生,提前谢谢

我有一个涉及生物学领域的问题.现在我有4个非常大的文件(每个有1亿行),但结构相当简单,这些文件的每一行只有2个字段,都代表一种基因.

我的目标是:设计一个可以实现以下目标的高效算法:在这4个文件的内容中找到一个圆圈.圆圈定义为:

field #1 in a line in file 1 == field #1 in a line in file 2 and
field #2 in a line in file 2 == field #1 in a line in file 3 and
field #2 in a line in file 3 == field #1 in a line in file 4 and
field #2 in a line in file 4 == field #2 in a line in file 1

我想不出一个解决这个问题的好方法,所以我现在只写了一个暴力 - 愚蠢的4层嵌套循环.我正在考虑将它们按字母顺序排序,即使这可能有点帮助,但是很明显计算机内存不允许我一次加载所有内容.有人能告诉我一个以时间和空间有效的方式解决这个问题的好方法吗？谢谢!!

我在接受采访时被问到这个问题.考虑穿孔卡的情况,其中每个穿孔卡具有64位模式.我被建议每张卡片int因为每个int都是一个位集合.

另外,我认为我有一个已经包含1000张这样的牌的阵列.我必须每次生成一个新元素,这与之前的1000张卡片不同.数组中的整数(也就是卡片)不一定要排序.

更重要的是,对于C++来说,问题64 bit int怎么可能呢？它来自何处？如何从数组中生成这个新卡,其中要生成的元素与数组中已存在的所有元素不同？

所以我没有通过编程面试问题

"鉴于一系列的整数1,2,......,n,其中一个缺失,找到丢失的一个."

面试官说正确答案是将数字相加并从n(n + 1)/ 2中减去总和,即应用公式https://en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_ %2B_%E2%8B%AF

并说任何计算机科学专业的学生都会这样做.我的解决方案就像

char takenSpots [] = n*malloc(sizeof(char)); 
for (int k = 0; k < n; ++k) takenSpots[arr[k]-1] = 'x';
for (int k = 0; k < n; ++k) if (takenSpots[k] != 'x') return (k+1);

这并不像我承认的总和解决方案那样"酷",我从未想过尝试过.

首先,使用求和方法是否存在溢出的危险？我的意思是,如果arr包含~((int)0)和~((int)0) - 1？那么不会arr[0] + arr[1] + ... + arr[n-1]溢出？或者解决方案是否仍然有效,因为1 + 2 + ... + n溢出？

问题：输入位于顺序文件上。该文件最多包含 40 亿个整数。找出缺失的整数。

根据我的理解解决方案：