gpt4 book ai didi

algorithm - 以 O(n) 复杂度对数组进行排序

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:13:01 26 4
gpt4 key购买 nike

我在 Atrenta 的面试中被问到一个有趣的问题。这是对复杂度为 O(n) 的数组进行排序,我说这是不可能的,但他坚持认为这是不可能的,即使在采访之后也是如此。

是这样的。

你有一个数组,比方说:[1,0,1,0,1,1,0],这需要排序。必须在数组中完成什么(从某种意义上说,不涉及其他数据结构。

我没有,而且我认为不可能以 O(n) 的复杂度进行任何排序。我能想到的最好的是 O(n * log n),我的知识来自维基百科。

如果您知道,请给我您的想法和实现方法。

最佳答案

在您的示例中,数组中只有两个不同的值,因此您可以使用计数排序:

zero_count = 0
for value in array:
if value == 0:
zero_count += 1
for i in 0 ... zero_count:
array[i] = 0
for i in zero_count ... array.size:
array[i] = 1

基数排序是更普遍适用的 O(n) 排序族。

比较排序平均需要 Omega(n * log n) 比较,因此不能在最坏情况或平均情况线性时间内运行。

关于algorithm - 以 O(n) 复杂度对数组进行排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13402602/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com