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