基于比较的算法,在线性时间内将最大元素与最小元素配对

问题描述 投票:0回答:1

给定一个整数数组。我想设计一个基于比较的算法,将最大的元素与最小的元素配对,第二个最小的元素与第二个最小的元素配对,依此类推。显然,如果我对数组进行排序,这很容易,但我想在O(n)时间内完成。我怎么可能解决这个问题?

algorithm
1个回答
4
投票

我可以证明它不存在。

让我们通过矛盾证明:假设有这样的算法

  • 当我们得到第k个最小和第k个最大对的数组时。
  • 我们可以通过按顺序获取所有分钟来获得排序数组,然后按顺序排列所有最大值,
  • 所以我们可以得到以O(n)步骤排序的原始数组。
  • 所以我们可以得到一个基于比较的排序算法,在O(n)中排序
  • 然而,可以证明基于比较的排序算法必须至少采用n个n步骤。 (许多在线证明。即qazxsw poi)
  • 因此我们有矛盾,所以这种算法不存在。
© www.soinside.com 2019 - 2024. All rights reserved.