-1

这是一个面试问题，我在很多地方都找到了答案。我必须承认我无法理解解决方案，所以我在这里提出问题寻求帮助：

Given an array having 16000 unique integers, each lying within the range 1 to 20000, how
do u sort it. U can load only 1000 numbers at a time in memory.

这是我遇到的一个解决方案，但我无法理解：http ://www.careercup.com/question?id=23123665

具体问题：

  • 作者是如何选择“625”的。我知道 20000/32 是 625，但它背后的逻辑是什么？
  • 作者如何使用除法和取模运算对数组进行排序？
4

1 回答 1

1

链接解决方案本质上是存储数字列表的紧凑直方图。每个直方图桶只接受一个数字，并且数字在列表中是唯一的，所以桶只需要从0到1（一位）计数。因此，每个存储桶有一个数字，您需要将 20,000 个存储桶存储在内存中。

您可以将 20,000 个一位存储桶打包成 625 个 32 位整数。您可以将整数数组视为一位值的二维数组，有 625 行和 32 列。要查找特定数字的存储桶，请使用 number/32 查找行，使用 number%32 查找列。

一旦您通过并计算列表中数字的存在，您的直方图可以按顺序写回作为排序列表。

于 2013-08-14T06:55:58.367 回答