寻找失踪的数字 [英] Find the numbers missing

问题描述

如果我们有所有的数字的多达N个（N小于10）的阵列，什么是找到所有缺失的数目的最佳方式。 例如：

If we have an array of all the numbers up to N (N < 10), what is the best way to find all the numbers that are missing. Example:

N = 5
1 5 3 2 3

Output: 1 5 4 2 3 

在恩，4号是缺少一个，并有2 3S，所以我们更换了第一个有4个，现在阵列完成 - 所有的数字高达5是否有

In the ex, the number 4 was the missing one and there were 2 3s, so we replaced the first one with 4 and now the array is complete - all the numbers up to 5 are there.

有没有什么简单的算法，能做到这一点？

Is there any simple algorithm that can do this ?

推荐答案

由于N是非常小的，可以使用F [i] = K，如果我数出现k次。

Since N is really small, you can use F[i] = k if number i appears k times.

int F[10]; // make sure to initialize it to 0
for ( int i = 0; i < N; ++i )
  ++F[ numbers[i] ];

现在，来取代重复，穿越你的电话号码数组，如果当前号码出现不止一次，减少它的数量，并将其与一个数字，出现0次更换和增加这个数字的计数。如果你一直没有出现在所有数字的列表，你可以保持这个O（​​N）。我会让你找出究竟需要做的事情，因为这听起来像功课。

Now, to replace the duplicates, traverse your number array and if the current number appears more than once, decrement its count and replace it with a number that appears 0 times and increment that number's count. You can keep this O(N) if you keep a list of numbers that don't appear at all. I'll let you figure out what exactly needs to be done, as this sounds like homework.

这篇关于寻找失踪的数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！