3

有一个包含 1000 个大数字（也可以是 64 位数字）的数组（大于 1000 个元素的空间）。数组中的数字不一定是排序的。
我们必须在第 1001 个位置生成一个与之前的 1000 不同的唯一数字。
证明使用的方法是最好的。

我的答案（不知道这在多大程度上是正确的）：对数字进行排序，然后从 0 位置开始。第 1000 位的数字 + 1 是所需的数字。

对此有更好的建议？

4

5 回答 5

4

创建一个包含 1001 个元素的辅助数组。将所有这些设置为 1（或 true 或 Y 或您选择的任何值）。遍历主数组，如果您在 1..1000 范围内找到一个数字，则将 0 输出（或伪造其他方式）辅助数组中的相应元素。最后，辅助数组中不为 0（或 false）的第一个元素对应于不在主数组中的数字。

这很简单，而且我认为时间复杂度为 O(n)，其中 n 是主数组中的元素数。

于 2012-06-06T13:31:05.453 回答
0 
unsigned ii,slot;

unsigned array [ NNN ];
/* allocate a histogram */
#define XXX (NNN+1);
unsigned histogram [XXX];
memset(histogram, 0, sizeof histogram);

for (ii=0; ii < NNN; ii++) {
        slot = array [ii ] % XXX;
        histogram[slot] += 1;
        }
for (slot=0; slot < NNN; slot++) {
        if ( !histogram[slot]) break;
        }

/* Now, slot + k * XXX will be a 
** number that does not occur in the original array */

注意：这类似于高性能标记，但至少我输入了代码......

于 2012-06-06T13:38:25.193 回答
0

如果对数组进行排序，则唯一编号有三种可能性：

  1. array[999]+1，如果 array[999] 不等于 INT_MAX
  2. array[0]-1，如果 array[0] 不等于 INT_MIN
  3. 数组[i] 和数组[i+1] 之间的数字，如果数组[i+1]-数组[i]>1 (0<=i<=998)。请注意，如果前两次尝试都失败了，那么可以保证数组中的两个元素之间存在一个数字。

请注意，此解决方案也适用于第 1002、第 1003 等。

于 2012-06-06T13:55:28.260 回答
0

尝试笨拙的 C# 实现

public class Test
{
    public List<int> Sequence { get; set; }

    public void GenerateFirstSequence()
    {
        Sequence = new List<int>();
        for (var i = 0; i < 1000; i++)
        {
            var x = new Random().Next(0, int.MaxValue);
            while (Sequence.Contains(x))
            {
                x = new Random().Next(0, int.MaxValue);
            }
            Sequence.Add(x);
        }
    }

    public int GetNumberNotInSequence()
    {
        var number = Sequence.OrderBy(x => x).Max();
        var mustRedefine = number == int.MaxValue && Sequence.Contains(number);
        if (mustRedefine)
        {
            while (Sequence.Contains(number))
            {
                number = number - 1;
                if (!Sequence.Contains(number))
                    return number;
            }
        }
        return number + 1;
    }
}
于 2012-06-06T14:08:41.607 回答
0

我对这个问题有一些想法：

您可以创建一个包含 1000 个元素的哈希表 H。假设您的数组名为 A，并且对于每个元素，我们都有 1000 的提醒：m[i] = A[i] % 1000。

如果A[i]和A[j]有冲突，那么A[i] % 1000 = A[j] % 1000。也就是说，必须存在一个索引k，没有元素的提醒1000等于到 k，那么 k 就是你要得到的数字。

如果根本没有冲突，只需选择 H[1] + 1000 作为结果。

该算法的复杂度为 O(l)，其中 l 表示原始列表大小，在示例中 l = 1000

于 2012-06-06T14:37:30.790 回答