令 A1,A2,...,An 为 [0,2k] 之间的实数(k 为常量)。已知对于任何一对 Ai,AJ 然后 |Ai-Aj|>=k/n,
描述一种在O(n) 运行时最坏情况下对数字进行排序的算法。
我知道答案应该是桶排序。不明白为什么，如果是这样，我该如何选择正确数量的桶？ |Ai-Aj|>=k/n 实际上有什么帮助？
最佳答案
条件 |Ai - Aj| ≥ k/n 表示如果将范围 [0, 2k] 分成 2n 个不同的桶(每个桶的大小为 2k/2n = k/n)，那么每个范围内最多只能有一个数字(除非可能数字位于桶的端点。)如果您更紧密地创建桶(例如，通过创建 3n 个桶)，那么每个桶的大小都小于 k/n，因此最多可以包含一个数字。
然后您可以使用桶排序算法对数字进行排序:
- 创建一个包含 3n 个桶的数组，每个桶代表范围 [(2k/3n)i, (2k/3n)(i + 1))
- 对于每个数字:
- 将该数字除以 (2k/3n) 以确定将其放入哪个桶中。
- 将数字放入该桶中。
- 对于每个桶:
- 如果该桶不为空，则将该桶中的数字写入结果数组。
第一步需要 O(n) 时间，因为您要创建一个大小为 3n 的数组。下一步需要时间 O(n)，因为您访问每个 O(n) 数字一次并在每一步做 O(1) 工作。最后一步也需要 O(n) 时间，因为您总共访问了 3n 个桶。
希望这对您有所帮助!
关于algorithm - 对 [0,2k] 之间的一系列 n 个数字进行排序，每对之间存在 : |Ai-Aj|>=k/n，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/17476561/