數組的最大值和最小值

給出了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

回答