首页 文章

找到一个不是40亿个给定值的整数

提问于
浏览 次
652

这是一个面试问题：

给定一个包含40亿个整数的输入文件，提供一个算法来生成一个未包含在文件中的整数 . 假设您有1 GB内存 . 如果您只有10 MB内存，请跟进您的操作 .

我的分析：

文件大小为4×109×4字节= 16 GB .

我们可以进行外部排序，因此我们可以了解整数的范围 . 我的问题是在排序的大整数集中检测缺失整数的最佳方法是什么？

我的理解（读完所有答案后）：

假设我们正在谈论32位整数 . 有2 ^ 32 = 4 * 109个不同的整数 .

情况1：我们有1 GB = 1 * 109 * 8位= 80亿位内存 . 解决方案：如果我们使用一个代表一个不同整数的位，那就足够了 . 我们不需要排序 . 执行：

int radix = 8;
byte[] bitfield = new byte[0xffffffff/radix];
void F() throws FileNotFoundException{
    Scanner in = new Scanner(new FileReader("a.txt"));
    while(in.hasNextInt()){
        int n = in.nextInt();
        bitfield[n/radix] |= (1 << (n%radix));
    }

    for(int i = 0; i< bitfield.lenght; i++){
        for(int j =0; j<radix; j++){
            if( (bitfield[i] & (1<<j)) == 0) System.out.print(i*radix+j);
        }
    }
}

情况2：10 MB内存= 10 * 106 * 8位= 80万位

Solution: For all possible 16-bit prefixes, there are 2^16 number of
integers = 65536, we need 2^16 * 4 * 8 = 2 million bits. We need build
65536 buckets. For each bucket, we need 4 bytes holding all possibilities because
 the worst case is all the 4 billion integers belong to the same bucket.

step1: Build the counter of each bucket through the first pass through the file.
step2: Scan the buckets, find the first one who has less than 65536 hit.
step3: Build new buckets whose high 16-bit prefixes are we found in step2
through second pass of the file
step4: Scan the buckets built in step3, find the first bucket which doesnt
have a hit.

The code is very similar to above one.

结论：我们通过增加文件传递来减少内存 .

对那些迟到的人的澄清：正如所提出的那样，问题并不是说文件中没有一个完整的整数 - 至少不是大多数人对它的解释 . 然而，评论主题 are 中的许多评论关于任务的变化 . 不幸的是， introduced 它对评论主题的评论后来被其作者删除了，所以现在看来孤立的回复只是误解了一切 . 这很令人困惑 . 抱歉 .

algorithm

30 回答

  • 7

    为什么要这么复杂？你问一个文件中没有的整数？

    根据指定的规则，您需要存储的唯一内容是您到目前为止在文件中遇到的最大整数 . 读取整个文件后，返回大于该值的数字1 .

    没有碰到maxint或任何东西的风险，因为根据规则，对整数的大小或算法返回的数字没有限制 .

    回复于
  • 9

    他们可能正在寻找你是否听说过概率Bloom Filter，它可以非常有效地确定一个值是否不是一个大集合的一部分，（但只能很有可能确定它是该集合的成员 . ）

    回复于
  • 139

    您可以使用位标志来标记是否存在整数 .

    遍历整个文件后，扫描每个位以确定该数字是否存在 .

    假设每个整数是32位，如果完成位标记，它们将方便地适合1 GB的RAM .

    回复于
  • 4

    出于某种原因，我一看到这个问题就想到了对角化 . 我假设任意大整数 .

    读第一个数字 . 用零位填充它，直到你有40亿位 . 如果第一个（高位）位为0，则输出1;否则输出0.（你真的不需要左键盘：如果数字中没有足够的位，你只输出一个 . ）对第二个数字做同样的事情，除了使用它的第二个数字 . 以这种方式继续浏览文件 . 您将一次输出一个40位的数字，并且该数字与文件中的任何数字都不相同 . 证明：它与第n个数字相同，然后他们会同意第n位，但它们不是通过构造 .

    回复于
  • 30

    统计通知算法使用比确定性方法更少的传递来解决此问题 .

    If very large integers are allowed 然后可以生成一个在O（1）时间内可能唯一的数字 . 像GUID这样的伪随机128位整数只会与集合中现有的40亿个整数中的一个冲突，而不是每640亿亿个案例中只有一个 .

    If integers are limited to 32 bits 然后可以使用远小于10 MB的单次传递生成一个可能唯一的数字 . 伪随机32位整数将与40亿现有整数中的一个冲突的几率约为93％（4e9 / 2 ^ 32） . 1000个伪随机整数全部碰撞的几率小于12,000亿亿（1个碰撞的概率^ 1000） . 因此，如果程序维护包含1000个伪随机候选者的数据结构并迭代已知整数，从候选者中消除匹配，则几乎肯定会找到至少一个不在文件中的整数 .

    回复于
  • 8

    Bit Elimination

    一种方法是消除位，但这可能实际上不会产生结果（很可能不会） . 伪代码：

    long val = 0xFFFFFFFFFFFFFFFF; // (all bits set)
foreach long fileVal in file
{
    val = val & ~fileVal;
    if (val == 0) error;
}

    Bit Counts

    跟踪位数;并使用金额最小的位生成一个值 . 同样，这无法保证生成正确的值 .

    Range Logic

    跟踪列表有序范围（按开始排序） . 范围由结构定义：

    struct Range
{
  long Start, End; // Inclusive.
}
Range startRange = new Range { Start = 0x0, End = 0xFFFFFFFFFFFFFFFF };

    浏览文件中的每个值，然后尝试将其从当前范围中删除 . 这种方法没有内存保证，但它应该做得很好 .

    回复于
  • 35

    如果它们是32位整数（可能选择约40亿个数字接近2 ^ 32），那么40亿个数字的列表将占用最多93％的可能整数（4 * 10 ^ 9 /（2 ^ 32）） . 因此，如果你创建一个2 ^ 32位的位数组，每个位初始化为零（这将占用2 ^ 29字节~500 MB的RAM;记住一个字节= 2 ^ 3位= 8位），读取你的整数列表并为每个int设置相应的位数组元素从0到1;然后读取你的位数组并返回仍然为0的第一位 .

    在RAM较少（~10 MB）的情况下，需要稍微修改此解决方案 . 对于0到83886079之间的所有数字，10 MB~83886080位仍然足以进行位数组 . 所以你可以阅读你的整体清单;并且只在位数组中记录0到83886079之间的#s . 如果数字是随机分布的;以极大的概率（它相差100％约10^-2592069）你会发现缺少int） . 事实上，如果你只选择数字1到2048（只有256字节的RAM），你仍然会发现一个失败的数字，压倒性的百分比（99.9999999999999999999999999999999999999999999995％）的时间 .

    但是，让我们说而不是大约有40亿个数字;你有2 ^ 32 - 1个数字和不到10 MB的RAM;因此，任何小范围的整数只有很小的可能性不包含该数字 .

    如果你保证列表中的每个int都是唯一的，你可以将数字相加并用一个＃缺省减去全部和（1/2）（2 ^ 32）（2 ^ 32-1）= 9223372034707292160找到缺少的int . 但是，如果int发生两次，则此方法将失败 .

    但是，你总能分而治之 . 一种天真的方法是读取数组并计算前半部分（0到2 ^ 31-1）和后半部分（2 ^ 31,2 ^ 32）的数字数量 . 然后选择数字较少的范围并重复将该范围分成两半 . （假设在（2 ^ 31,2 ^ 32）中有两个较少的数字，那么你的下一个搜索将计算范围内的数字（2 ^ 31,3 * 2 ^ 30-1），（3 * 2 ^ 30， 2 ^ 32） . 继续重复，直到找到一个数字为零的范围并且你有答案 . 应该通过数组取O（lg N）~32个读数 .

    那种方法效率低下 . 我们在每一步中只使用两个整数（或大约8字节的RAM和一个4字节（32位）整数） . 更好的方法是划分为sqrt（2 ^ 32）= 2 ^ 16 = 65536个bin，每个bin在bin中有65536个数字 . 每个bin需要4个字节来存储其计数，因此您需要2 ^ 18个字节= 256 kB . 所以bin 0是（0到65535 = 2 ^ 16-1），bin 1是（2 ^ 16 = 65536到2 * 2 ^ 16-1 = 131071），bin 2是（2 * 2 ^ 16 = 131072到3） * 2 ^ 16-1 = 196607） . 在python中你会有类似的东西：

    import numpy as np
nums_in_bin = np.zeros(65536, dtype=np.uint32)
for N in four_billion_int_array:
    nums_in_bin[N // 65536] += 1
for bin_num, bin_count in enumerate(nums_in_bin):
    if bin_count < 65536:
        break # we have found an incomplete bin with missing ints (bin_num)

    读完~40亿整数列表;并计算每个2 ^ 16箱中有多少总量，并找到一个不包含全部65536个数字的incomplete_bin . 然后你再次阅读40亿整数列表;但这次只注意整数在那个范围内;当你找到它们时翻转一下 .

    del nums_in_bin # allow gc to free old 256kB array
from bitarray import bitarray
my_bit_array = bitarray(65536) # 32 kB
my_bit_array.setall(0)
for N in four_billion_int_array:
    if N // 65536 == bin_num:
        my_bit_array[N % 65536] = 1
for i, bit in enumerate(my_bit_array):
    if not bit:
        print bin_num*65536 + i
        break
    回复于
  • 16

    对于10 MB内存约束：

    • 将数字转换为二进制表示 .

    • 创建二叉树，其中left = 0且right = 1 .

    • 使用二进制表示法在树中插入每个数字 .

    • 如果已插入数字，则已经创建了叶子 .

    完成后，只需使用之前未创建的路径创建请求的号码 .

    40亿个数字= 2 ^ 32，意味着10 MB可能还不够 .

    EDIT

    可以进行优化，如果已经创建了两个端叶并且具有公共父级，则可以删除它们并将父标记为不是解决方案 . 这削减了分支并减少了对内存的需求 .

    EDIT II

    也没有必要完全构建树 . 如果数字相似，您只需要构建深分支 . 如果我们也削减了分支，那么这个解决方案可能会起作用 .

    回复于
  • 6

    根据原问题中的当前措辞，最简单的解决方案是：

    找到文件中的最大值，然后向其中添加1 .

    回复于
  • 3

    2128 * 1018 1（即（28）16 * 1018 1） - 今天不能成为一个普遍的答案吗？这表示无法保存在16 EB文件中的数字，这是当前任何文件系统中的最大文件大小 .

    回复于
  • 187

    正如Ryan基本上说的那样，对文件进行排序，然后查看整数，当跳过一个值时，你就可以了:)

    EDIT at downvoters：OP提到文件可以排序，所以这是一个有效的方法 .

    回复于
  • 14

    使用 BitSet . 在每个字节8个打包到BitSet中的40亿个整数（假设最多2 ^ 32个整数）是2 ^ 32/2 ^ 3 = 2 ^ 29 =大约0.5 Gb .

    要添加更多细节 - 每次读取数字时，请在BitSet中设置相应的位 . 然后，对BitSet进行一次传递，找到第一个不存在的数字 . 事实上，你可以通过反复选择一个随机数并测试它是否存在来做到这一点 .

    实际上BitSet.nextClearBit（0）会告诉你第一个非设置位 .

    查看BitSet API，它似乎只支持0..MAX_INT，因此您可能需要2个BitSet - 一个用于've数字，一个用于-'ve-数字 - 但内存要求不会改变 .

    回复于
  • 24

    对于1 GB RAM变体，您可以使用位向量 . 您需要分配40亿位== 500 MB字节数组 . 对于从输入读取的每个数字，将相应位设置为“1” . 完成后，迭代这些位，找到第一个仍为“0”的位 . 它的索引就是答案 .

    回复于
  • 3

    欺骗问题，除非被引用不当 . 只需读取文件一次即可获得最大整数 n ，并返回 n+1 .

    当然你需要一个备份计划以防 n+1 导致整数溢出 .

    回复于
  • 9

    只要我们做出创造性的答案，这里就是另一个 .

    使用外部排序程序以数字方式对输入文件进行排序 . 这适用于您可能拥有的任何内存量（如果需要，它将使用文件存储） . 读取已排序的文件并输出缺少的第一个数字 .

    回复于
  • 112

    关于这个问题的详细讨论已在Jon Bentley "Column 1. Cracking the Oyster"编程珍珠Addison-Wesley pp.3-10

    Bentley讨论了几种方法，包括外部排序，使用多个外部文件进行合并排序等 . 但Bentley建议的最佳方法是使用bit fields的单程算法，他幽默地称之为"Wonder Sort" :)即将出现问题，可以表示40亿个数字在：

    4 billion bits = (4000000000 / 8) bytes = about 0.466 GB

    实现bitset的代码很简单:(取自solutions page）

    #define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1 + N/BITSPERWORD];

void set(int i) {        a[i>>SHIFT] |=  (1<<(i & MASK)); }
void clr(int i) {        a[i>>SHIFT] &= ~(1<<(i & MASK)); }
int  test(int i){ return a[i>>SHIFT] &   (1<<(i & MASK)); }

    Bentley的算法对文件进行单次传递，然后使用上面的 test 宏检查此数组，以查找丢失的数字 .

    如果可用内存小于0.466 GB，Bentley建议使用k-pass算法，该算法根据可用内存将输入划分为范围 . 举一个非常简单的例子，如果只有1个字节（即处理8个数字的存储器）可用且范围从0到31，我们将其分为0到7,8-15,16-22的范围，依此类推并在每个 32/8 = 4 次传球中处理此范围 .

    HTH .

    回复于
  • 4

    EDIT 好的，这不是't quite thought through as it assumes the integers in the file follow some static distribution. Apparently they don' t需要，但即使这样，也应该尝试这个：

    有大约43亿个32位整数 . 我们不知道它们是如何在文件中分布的，但最坏的情况是具有最高香农熵的那个：相等的分布 . 在这种情况下，文件中不出现任何一个整数的概率

    （（2³²-1）/2³²）⁴⁰⁰⁰⁰⁰⁰⁰⁰⁰≈.4

    香农熵越低，这个概率在平均值上越高，但即使对于这种最坏的情况，我们也有90％的机会在随机整数进行5次猜测后找到一个非发生的数字 . 只需使用伪随机生成器创建此类数字，将它们存储在列表中 . 然后在int之后读取int并将其与所有猜测进行比较 . 如果匹配，请删除此列表条目 . 经过所有文件后，你可能会有不止一个猜测 . 使用其中任何一个 . 在罕见的（甚至在最坏的情况下为10％）无法猜测的事件中，获得一组新的随机整数，这次可能更多（10-> 99％） .

    内存消耗：几十个字节，复杂度：O（n），开销：可以选择，因为大部分时间都花在不可避免的硬盘访问上，而不是比较整数 .

    当我们不假设静态分布时，实际最坏的情况是每个整数都出现最大值 . 曾经，因为那时只有1 - 4000000000 /2³²≈6％的整数需要更多的猜测，但这仍然不会损害大量内存 .

    回复于
  • 44

    Assuming that "integer" means 32 bits ：拥有10 MB的空间足以让您计算输入文件中具有任何给定16位前缀的数量，对于通过输入文件的所有可能的16位前缀 . 至少一个桶的击中次数将少于2 ^ 16次 . 执行第二次传递以查找已使用该存储桶中的哪些可能数字 .

    If it means more than 32 bits, but still of bounded size ：如上所述，忽略恰好落在（有符号或无符号;您选择的）32位范围之外的所有输入数字 .

    If "integer" means mathematical integer ：读取输入一次并跟踪您完成的最长数字的最大数字长度，输出最大加一个随机数再增加一位数 . （文件中的一个数字可能是一个超过10 MB的bignum来准确表示，但如果输入是一个文件，那么你至少可以表示适合它的任何东西的长度） .

    回复于
  • 5

    如果没有大小限制，最快的方法是获取文件的长度，并生成文件长度1个随机数字（或只是“11111 ...”s） . 优点：您甚至不需要读取文件，并且可以将内存使用率降至最低 . 缺点：您将打印数十亿位数字 .

    但是，如果唯一的因素是最小化内存使用，而其他任何事情都不重要，那么这将是最佳解决方案 . 它甚至可能会让你“滥用规则”奖 .

    回复于
  • 8

    仅仅为了完整起见，这是另一个非常简单的解决方案，它很可能需要很长时间才能运行，但使用的内存非常少 .

    假设所有可能的整数都是 int_min 到 int_max 的范围，而 bool isNotInFile(integer) 是一个函数，如果文件不包含某个整数，则返回true，否则为false（通过将该特定整数与文件中的每个整数进行比较）

    for (integer i = int_min; i <= int_max; ++i)
{
    if (isNotInFile(i)) {
        return i;
    }
}
    回复于
  • 53

    我将回答1 GB版本：

    问题中没有足够的信息，所以我先说一些假设：

    整数是32位，范围-2,147,483,648到2,147,483,647 .

    伪代码：

    var bitArray = new bit[4294967296];  // 0.5 GB, initialized to all 0s.

foreach (var number in file) {
    bitArray[number + 2147483648] = 1;   // Shift all numbers so they start at 0.
}

for (var i = 0; i < 4294967296; i++) {
    if (bitArray[i] == 0) {
        return i - 2147483648;
    }
}
    回复于
  • 6

    检查大小输入文件，然后输出任何数字 too large to be represented by a file that size. 这可能看起来像一个廉价的技巧，但它's a creative solution to an interview problem, it neatly sidesteps the memory issue, and it'技术上是O（n） .

    void maxNum(ulong filesize)
{
    ulong bitcount = filesize * 8; //number of bits in file

    for (ulong i = 0; i < bitcount; i++)
    {
        Console.Write(9);
    }
}

    应该打印 10 bitcount - 1 ，它将始终大于 2 bitcount . 从技术上讲，你必须击败的数字是 2 bitcount - (4 * 109 - 1) ，因为你知道文件中有（40亿 - 1）个其他整数，即使有完美的压缩，它们每个也会占用至少一位 .

    回复于
  • 5

    由于问题没有指定我们必须找到文件中不存在的最小可能数字，我们只能生成一个比输入文件本身更长的数字 . :)

    回复于
  • 3

    • 最简单的方法是在文件中找到最小数字，并返回少于1的数字 . 这使用O（1）存储，并且对于n个数字的文件使用O（n）时间 . 但是，如果数字范围有限，它将失败，这可能使min-1不是一个数字 .

    • 已经提到了使用位图的简单直接的方法 . 该方法使用O（n）时间和存储 .

    • 还提到了具有2 ^ 16个计数桶的2遍方法 . 它读取2 * n个整数，因此使用O（n）时间和O（1）存储，但它不能处理超过2 ^ 16个数字的数据集 . 然而，通过运行4次传递而不是2次传递，它很容易扩展到（例如）2 ^ 60 64位整数，并且通过仅使用尽可能多的存储器并且相应地增加传递次数，可以轻松地适应使用微存储器 . 哪种情况下运行时间不再是O（n）而是O（n * log n） .

    • 迄今为止由rfrankel和ircmaxell提及的所有数字进行异或的方法回答了stackoverflow#35185中提出的问题，正如ltn100指出的那样 . 它使用O（1）存储和O（n）运行时 . 如果目前我们假设32位整数，则XOR产生不同数字的概率为7％ . 理由：给定~4.5个不同的数字XOR 'd together, and ca. 300M not in file, the number of set bits in each bit position has equal chance of being odd or even. Thus, 2^32 numbers have equal likelihood of arising as the XOR result, of which 93% are already in file. Note that if the numbers in file aren' t全部不同，XOR方法的成功概率上升 .

    回复于
  • 2

    如果你不是悲观主义者的话 . 碰撞的可能性是 1 in 2^64/(4*10^9) = 4611686018.4 （约为40亿分之一） . 大多数时候你都是对的！

    （开玩笑......好吧 . ）

    回复于
  • 26

    这可以使用二进制搜索的变体在非常小的空间中解决 .

    • 从允许的数字范围开始， 0 到 4294967295 .

    • 计算中点 .

    • 遍历文件，计算有多少数字相等，小于或高于中点值 .

    • 如果没有数字相等，你就完成了 . 中点数是答案 .

    • 否则，选择编号最少的范围，并使用此新范围从步骤2开始重复 .

    这将需要通过文件最多32次线性扫描，但它只会使用几个字节的内存来存储范围和计数 .

    这基本上与Henning's solution相同，除了它使用两个箱而不是16k .

    回复于
  • 12

    如果您在[0,2 ^ x - 1]范围内缺少一个整数，那么只需将它们全部放在一起 . 例如：

    >>> 0 ^ 1 ^ 3
2
>>> 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 6 ^ 7
5

    （我知道这并没有完全回答这个问题，但对于一个非常相似的问题，这是一个很好的答案 . ）

    回复于
  • 5

    如果我们假设数字范围总是2 ^ n（2的偶数幂），则排他性或将起作用（如另一张海报所示） . 至于原因，我们来证明一下：

    理论

    给定任何基于0的整数范围，其中包含缺少一个元素的 2^n 元素，您可以通过简单地将已知值相加以产生缺失的数字来找到缺少的元素 .

    证明

    让我们看看n = 2.对于n = 2，我们可以表示4个唯一的整数：0,1,2,3 . 它们的位模式为：

    • 0 - 00

    • 1 - 01

    • 2 - 10

    • 3 - 11

    现在，如果我们看一下，每个位都设置了两次 . 因此，由于它被设置为偶数次，并且数字的异或将产生0.如果缺少单个数字，则排除 - 或将产生一个数字，当与缺少的数字进行排他时将导致因此，缺失的数字和由此产生的排他性数字完全相同 . 如果我们删除2，则得到的xor将是 10 （或2） .

    现在，让's look at n+1. Let'调用 n ， x 中设置每个位的次数以及 n+1 y 中每个位的设置次数 . y 的值将等于 y = x * 2 ，因为有 x 元素， n+1 位设置为0， x 元素 n+1 位设置为1.由于 2x 将始终为偶数， n+1 将始终设置每个位偶数次 .

    因此，由于 n=2 有效，并且 n+1 有效，因此xor方法将适用于 n>=2 的所有值 .

    基于0的范围的算法

    这很简单 . 它使用2 * n位内存，因此对于<= 32的任何范围，2个32位整数将起作用（忽略文件描述符消耗的任何内存） . 它只传递一次文件 .

    long supplied = 0;
long result = 0;
while (supplied = read_int_from_file()) {
    result = result ^ supplied;
}
return result;

    基于任意的范围算法

    该算法适用于任何起始编号到任何结束编号的范围，只要总范围等于2 ^ n ...这基本上重新定义范围，使最小值为0.但它确实需要2次通过通过文件（第一个获取最小值，第二个来计算缺少的int） .

    long supplied = 0;
long result = 0;
long offset = INT_MAX;
while (supplied = read_int_from_file()) {
    if (supplied < offset) {
        offset = supplied;
    }
}
reset_file_pointer();
while (supplied = read_int_from_file()) {
    result = result ^ (supplied - offset);
}
return result + offset;

    任意范围

    我们可以将这种修改的方法应用于一组任意范围，因为所有范围将至少跨越2 ^ n的幂 . 这仅在存在单个缺失位时才有效 . 它需要2次未分类的文件，但每次都会找到一个缺失的数字：

    long supplied = 0;
long result = 0;
long offset = INT_MAX;
long n = 0;
double temp;
while (supplied = read_int_from_file()) {
    if (supplied < offset) {
        offset = supplied;
    }
}
reset_file_pointer();
while (supplied = read_int_from_file()) {
    n++;
    result = result ^ (supplied - offset);
}
// We need to increment n one value so that we take care of the missing 
// int value
n++
while (n == 1 || 0 != (n & (n - 1))) {
    result = result ^ (n++);
}
return result + offset;

    基本上，重新定义范围大约为0.然后，它计算要附加的未排序值的数量，因为它计算异或 . 然后，它将未排序值的计数加1，以处理缺失值（计算丢失的值） . 然后，保持x值n值，每次递增1，直到n为2的幂 . 然后结果重新回到原始基数 . 完成 .

    这是我在PHP中测试的算法（使用数组而不是文件，但概念相同）：

    function find($array) {
    $offset = min($array);
    $n = 0;
    $result = 0;
    foreach ($array as $value) {
        $result = $result ^ ($value - $offset);
        $n++;
    }
    $n++; // This takes care of the missing value
    while ($n == 1 || 0 != ($n & ($n - 1))) {
        $result = $result ^ ($n++);
    }
    return $result + $offset;
}

    在一个包含任何值范围的数组中（我测试包括底片），其中一个在该范围内缺失，每次都找到正确的值 .

    另一种方法

    既然我们可以使用外部排序，为什么不检查差距呢？如果我们假设在运行此算法之前对文件进行了排序：

    long supplied = 0;
long last = read_int_from_file();
while (supplied = read_int_from_file()) {
    if (supplied != last + 1) {
        return last + 1;
    }
    last = supplied;
}
// The range is contiguous, so what do we do here?  Let's return last + 1:
return last + 1;
    回复于
  • 514

    从文件中删除空格和非数字字符并追加1.您的文件现在包含原始文件中未列出的单个数字 .

    来自Carbonetc的Reddit .

    回复于
  • 17

    我认为这是一个已解决的问题（见上文），但有一个有趣的侧面案例要记住，因为它可能会被问到：

    如果确实有4,294,967,295（2 ^ 32 - 1）个32位整数没有重复，因此只有一个缺失，那么有一个简单的解决方案 .

    在零处开始运行总计，并且对于文件中的每个整数，添加具有32位溢出的整数（实际上，runningTotal =（runningTotal nextInteger）％4294967296） . 完成后，将4294967296/2添加到运行总计中，再次使用32位溢出 . 从4294967296中减去它，结果是缺少的整数 .

    “只有一个缺失的整数”问题只能通过一次运行来解决，并且只有64位专用于数据的RAM（32表示运行总计，32表示读取下一个整数） .

    推论：如果我们不关心整数结果必须具有多少位，则更通用的规范非常容易匹配 . 我们只生成一个足够大的整数，它不能包含在我们给出的文件中 . 同样，这占用了绝对最小的RAM . 看到伪代码 .

    # Grab the file size
fseek(fp, 0L, SEEK_END);
sz = ftell(fp);
# Print a '2' for every bit of the file.
for (c=0; c<sz; c++) {
  for (b=0; b<4; b++) {
    print "2";
  }
}
    回复于

相关问题