给定一个整数数组。我想设计一个基于比较的算法 将最大的元素与最小的元素配对，将第二大的元素与第二小的元素配对，依此类推。显然，如果我对数组进行排序，这很容易，但我想在 O(n) 时间内完成。我怎样才能解决这个问题？
最佳答案
我可以证明它不存在。
反证法:假设有这样的算法
- 当我们可以获得第 k 个最小值和第 k 个最大值对的数组时。
- 我们可以通过按最小值排序然后按最大值排序来获得排序数组，
- 这样我们就可以在 O(n) 步中对原始数组进行排序。
- 所以我们可以得到一个基于比较的排序算法，在 O(n) 中排序
- 然而可以证明，基于比较的排序算法必须至少采用 n 记录 n 个步骤。 (网上有很多证明。即https://www.geeksforgeeks.org/lower-bound-on-comparison-based-sorting-algorithms/)
- 因此我们有一个矛盾所以这样的算法不 存在。
关于algorithm - 基于比较的算法，在线性时间内将最大元素与最小元素配对，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/55209579/