Nim*_*rod 2 java arrays sorting algorithm
我找到了这个答案:在一组数字中找到缺失数字的最快方法,当你只有一个数字丢失时这很好.
继续这个问题 - 我想知道找到所有缺失数字的最佳(和最快)方法是什么,以及对未排序数组进行排序.(例如,数组就像链接问题中描述的那样 - 数组大小为100,随机数为1-100,但其中一些缺失)
显然这些数字在一定范围内,或者谈论缺少数字是没有意义的.因此,可以应用计数排序.然后通过阵列进行线性扫描以找到孔.或者,您可以扫描排序步骤中的计数以查找缺少的元素.
这一切都在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次,2次3次,1次4次,依此类推.
1 1 3 3 4 6 7 8 9 10