我最近在面试中被问到这个问题。
给定一个包含负数和正数的排序整数数组,如何根据元素的绝对值对该数组进行求值?
这必须严格在 O(n) 时间内完成。
Input
{-9,-7,-3,1,6,8,14}
Output
{1,-3,6,-7,8,-9,14}
除了 O(n) 时间之外还有哪些可能的解决方案?
最佳答案
基本上,我们将有 2 个头,一个在数组的末尾,一个在开头。
v v
{-9, -7, -3, 1, 6, 8, 14}
我们比较我们的头指向的 2 个条目的绝对值,并将较大的插入到我们新的排序数组中。所以这里是 14。
New array: {14}
然后我们将我们选择的任何项目的头部移近中心。所以在这里我们将头指向 14 到 8。
v v
{-9, -7, -3, 1, 6, 8, 14}
然后我们重复这个过程,将两个绝对值中较大的一个插入到我们新的排序数组的开头。这里是-9,如|-9| > |8|
New array: {-9, 14}
在我们再次移动头部之后:
v v
{-9, -7, -3, 1, 6, 8, 14}
重复直到两个头在中心相遇
关于c# - 在严格的 O(n) 时间内对整数数组进行排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29184367/