找到一个数组的中间元素

Question

可能重复：
如何在O(n)的时间复杂度下找到长度为n的未排序数组中第k个最大的元素？ 大家好， 我在面试中遇到了一个问题。

问题：

整数数组将作为输入给出，你应该在不排序的情况下找出排序后的中间元素。

例如。 输入：1,3,5,4,2 输出: 3 当你对给定的输入数组进行排序时，它将是1,2,3,4,5，其中中间元素是3。 你应该在一次遍历中找到这个元素，而无需排序。

有什么解决方案吗？

- senthil

---

还有其他限制吗？元素的数量会是奇数吗？ - Mariy

重复的问题，链接为：https://dev59.com/UnVC5IYBdhLWcg3wjyDu。 - Jon

这是否总是一个从1到n的n个连续数字序列？ - Gumbo

应该使用C语言。是的，元素数量将是奇数。不，它不是一个序列。可以按任何顺序排列，如100、9、35、7、23，输出将为23。 - senthil

Answer 1

这是一个时间复杂度为O(n)的选择算法问题。 编辑：但如果你确定元素是连续的，你可以在一次遍历中计算最小值、最大值和元素数量，并返回[最小值 + (最大值 - 最小值 + 1)/2]。

- Saeed Amiri

---

不，它们不是连续的。可以是任意顺序。例如34、19、45、12、2，答案应该是19。 - senthil

@senthil，这样我的第一个答案就是你想要的了，阅读并搜索相关内容以理解它。 - Saeed Amiri

Answer 2

在我看来，你可以直接使用std::nth_element - 不知道这是否是一个可接受的答案。

- Johan Kotlinski

Answer 3

你可以使用“修改过的”快速排序来找到它。 时间复杂度为O(n^2)，但平均情况下速度应该相当快。您所做的是每次选择枢轴时，都要检查小于枢轴的元素数量和大于枢轴的元素数量。如果小于枢轴的元素数量和大于枢轴的元素数量相同，则枢轴是中位数。如果不是，则可以递归到包含元素的部分。最坏情况下，您将执行完全排序。

例子：

具有7个元素的数组，我们正在寻找第4个最小元素。

5 3 8 6 7 1 9

假设快速排序选择3作为枢轴，那么您将获得：

1 3 5 8 6 7 9

现在，您想在子数组[5、8、6、7、9]中找到第2个最小值。继续操作，直到枢轴成为当前迭代中正在搜索的第k个最小值。

我认为这个解决方案对于面试问题来说还不错，尽管您应该提到有一个O(n)确定性解决方案。

- Piva