我找到了这个答案:Quickest way to find missing number in an array of numbers ,当您只缺少一个数字时,这非常有用。
对于这个问题,我想知道找到所有缺失数字并对未排序数组进行排序的最佳(也是最快)方法是什么。 (例如,数组类似于链接问题中描述的数组 - 数组大小为 100,随机数为 1-100,但其中一些缺失)
最佳答案
显然这些数字都在一定范围内,否则谈论缺失的数字就没有意义。因此counting sort可以应用。然后对阵列进行线性扫描以找到孔。或者,您可以扫描排序步骤中的计数以查找丢失的元素。
这一切都在 O(n) 内运行。
示例: 以下数组给出 6,1,7,8,3,4,9,1,10,3。
现在通过遍历数组并增加每个遇到的数字的计数来计算每个数字在数组中出现的频率:
number 1 2 3 4 5 6 7 8 9 10
count 2 0 2 1 0 1 1 1 1 1
您立即发现 2 和 5 确实出现了 0 次,因此丢失了。
计数也可用于得出排序数组:我们需要 2 乘以 1、两次乘以 3、一次乘以 4,依此类推。
1 1 3 3 4 6 7 8 9 10
关于java - 找到未排序数组中所有缺失数字的最快方法是什么,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37859088/