主页 / coding / 问题 / 79556915
Accepted
user30176973
Asked: 2025-04-05 19:50:14 +0800 CST

如何在 O(n) 时间内对最多有 √n 个错误元素的几乎排序数组进行排序？

  • 772

你好，我尝试解决下面这个问题已经 5 个小时了，但还是没找到答案。这个问题的标题是“线性排序”，所以我假设最优答案的时间复杂度应该是 O(n)。问题如下。

=======================================================

假设你有一个包含 n 个整数的数组，最初按升序排列。但是，数组中元素对之间最多进行了⌊√n/2⌋次任意交换。因此，最多有 √n 个元素可能偏离了正确的位置。你必须使用时间复杂度尽可能低的算法将此数组重新排序为升序。

=======================================================

目前我发现，如果能在 O(n) 的时间复杂度内找出哪些元素位置不对，那么排序本身也应该花费 O(n)。不过我现在也不知道该怎么办了 :(

算法线性排序(A):

n ← length(A)
misplacedIndices ← empty set

// Step 1: Identify indices of potentially misplaced elements
   misplacedIndices.add(i) // Do this somehow(!!!!)


// sort indices in ascending order -> takes O(√n · log(√n))
misplacedIndices ← sorted(misplacedIndices)

// Step 2: Separate misplaced elements from correctly placed ones
misplacedList ← empty list
remainderList ← empty list
for i ← 0 to n - 1 do:
    if i ∈ misplacedIndices then:
        misplacedList.append(A[i])
    else:
        remainderList.append(A[i])
end for

// Sort the misplaced elements (only up to O(√n) elements)
sort(misplacedList)  // Time complexity: O(√n · log√n)

// Step 3: Merge the two sorted lists (remainderList and misplacedList)
result ← empty list
i ← 0, j ← 0
while i < length(remainderList) and j < length(misplacedList) do:
    if remainderList[i] ≤ misplacedList[j] then:
        result.append(remainderList[i])
        i ← i + 1
    else:
        result.append(misplacedList[j])
        j ← j + 1
end while

// Append any remaining elements from either list
while i < length(remainderList) do:
    result.append(remainderList[i])
    i ← i + 1
end while

while j < length(misplacedList) do:
    result.append(misplacedList[j])
    j ← j + 1
end while

return result
algorithm

2 个回答

  1. Best Answer

    遍历数组。每当 a[i] > a[i+1] 时，将两者移入一个单独的数组。这需要 n 步完成。该单独数组的大小最多为 2 sqrt n。您需要 O(2 sqrt n log sqrt n) = O(n) 步对其进行排序，然后再 O(n) 步将其合并到原始数组中。

    如果最多有 O(n / log n) 个元素位置错误，则总操作数实际上是 O(n)，这比 O(sqrt n) 要大得多。例如，对于一百万个元素，你可以处理 50,000 个元素位置错误，而不仅仅是 1,000 个。

    • 4

  2. 我认为一个非常简单的算法就可以实现并且是 O(n)，因为数组的属性如下：

    1. 将数组中无序元素 (a[i] > a[i+1]) 截断。这样最多可以得到 sqrt(n) + 1 个有序序列。

    2. 按第一个数字对序列进行排序。

    3. 创建结果数组。

    4. 继续从第一个序列插入，直到其当前元素大于第二个序列的第一个（即当前）元素。

    5. 将第一个序列插入到正确的位置，使序列再次按其当前元素排序。如果序列列表存储在最小堆中（当前元素作为键），则需要 O(log(sqrt(n))) = O(log(n))，但在列表中简单地插入 O(sqrt(n)) 也足以满足 O(n) 的整体性能要求。

    6. 从 4 处继续，直到所有元素都被插入（并且所有子序列都被消耗）。

    为什么是 O(n)？因为只有 sqrt(n) 个元素可以错位，所以我们必须执行步骤 5，最多 2 * sqrt(n) 次，并且 O(sqrt(n) * log(n)) < O(n)，因为 O(log(n)) < O(sqrt(n))，因此 O(n) = O(sqrt(n) * sqrt(n)) > O(sqrt(n) * log(n))。如果我们在步骤 5 中采用简单的 O(sqrt(n)) 方法，那么我们会得到 O(n)，但这是总和，所以只有 a + O(n)，并且整个算法仍然是 O(n)。

    • 3

相关问题