c - 数组的最大值和最小值

Question

给出了一个包含 n 个数字的数组，其中 n 是偶数。需要确定这 n 个数字的最大值和最小值。我需要知道所需的比较？

Answer 1

可以使用3*n/2-2比较来完成。

对于n == 2，只需比较两个数字。现在假设我们有第一个n-2数字的最小值和最大值。比较剩余的两个数字，然后将较大的与先前的最大值进行比较，将较小的与先前的最小值进行比较。

Answer 2

它可以在 O(n) 时间内完成。

您可以查看此链接以供参考

Answer 3

对于未排序的数组，可以通过近似1.5n比较来完成。您可以通过比较数组的元素对并存储min和 local来做到这一点max。您已经进行了n/2比较以找到（本地）最大值并n/2找到最小值。因此，共n处于这个阶段。

现在你遍历最大和最小局部变量并找到全局最大值和最小值。这也需要n/2比较。因此n + n / 2 = 1.5n。

如果数组已排序，则无需任何比较即可找到它，因为最小的数字在位置 0 上，而最大的数字在位置 N - 1 上。