数组的最大值和最小值

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

提示：3 * N/2-2的比较是不够。 – Henrik 2013-03-14 15:36:13

@亨利克可以请你详细说明 – user2170497 2013-03-14 15:37:45

它可以在O（n）时间完成。

您可以参考

2013-03-14 15:36:11

你在开玩笑吧？使用天真的方法可以在O（N） – 2013-03-14 15:36:55

@IvayloStrandjev完成： - 请纠正我，如果我错了，但我已经认为它是一个二维数组。那么二维阵列中也有可能是O（n）时间吗？ – 2013-03-14 15:39:24

'给出n个数字的数组，其中n是偶数。这n个数字的最大值和最小值都需要确定。“这里我没有提到任何2D。 OP要求以最少的比较次数查找n个数字中的最小和最大数字 – 2013-03-14 15:41:39

它可以通过3*n/2-2比较来完成看看这个link。

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

2013-03-14 15:39:47 Henrik

对于未排序的数组，可以在大约1.5n比较中完成。您可以通过比较数组的元素对并存储min和本地max。您已完成n/2比较以查找（当地人）最大值和n/2以查找最小值。因此，在这个阶段共有n。

现在，您可以查看最大和最小当地人并查找全局最大值和最小值。这也需要n/2比较。因此n + n/2 = 1.5n。

如果数组进行排序，你可以找到它没有任何的比较，因为最小的数字是0位置，最高上的位置N - 1

2013-03-14 16:02:12 dreamcrash

回答