我被问到一个很好的编程问题：
在输入中，我有 0-255（1 个字节）的 100 个唯一数字。我一次只能读一个数字，而且只能读一次。我有 40 字节的内存可供使用。目标是对所有数字进行排序并将它们打印在输出中。我确信数字的唯一性非常重要。
有任何想法吗？
问问题
599 次
2 回答
21
32 字节为您提供 256 位，足以维护在输入中看到的 256 个可能字节值中的哪一个的位图。一个额外的字节用于存储输入值。读取每个值，在位图中标记，然后丢弃。一旦您读取了所有 100 个输入值，只需写出与您在位图中设置的位相关的值。
然后问你应该如何处理其他 7 个字节:)
于 2013-05-23T18:48:19.290 回答
12
由于您的数字是唯一的并且它们只有 1 字节长，因此它们必须在 0 到 255 之间。将 40 字节的存储空间视为长位向量。当您阅读每个数字时，请在此 320 位位向量中设置适当的位。读完输入后，转身扫描这个位向量，打印出每个设置位对应的数字。
作为对@JavaNewb 的回应，这里有更多细节。首先，由于一个字节包含 8 位，它只能假设 256 个可能值中的一个，即 0 到 255。有了这个小事实，您可以查看您拥有的 40 字节存储阵列。这个数组原来有 40 字节 * 8 位/字节 = 320 位。由于问题表明 100 个 1 字节数字中的每一个都是唯一的，因此您知道您最多会看到一个特定数字（范围从 0 到 255）。每次看到一个数字，就在 40 字节数组中设置相应的位。例如，如果遇到数字 50，则在字节编号 6 中设置位编号 2。数字 N 对应N%8于字节中的位N/8. 保证您永远不会在此数组中遇到设置位，因为这意味着 100 个数字中存在重复项。读完所有数字后，查看 40 字节数组。此数组中设置的每个位对应于您读入的 100 个数字之一。通过从第 0 字节的第 0 位一直到第 31 字节的第 7 位遍历这个 40 字节数组，您将：
- 捕获所有读入的数字
- 按排序顺序观察它们
您现在所要做的就是在遍历 40 字节数组时打印与设置位相对应的数字。
于 2013-05-23T18:48:18.967 回答