java - 如何仅进行 "n"比较从文本文件中查找最小值和最大值？

Question

所以我有一个文件，里面有 n 个整数。我需要找到一种方法在找到最小值和最大值而不是 2n 次比较时进行 n 次比较。我当前的代码进行 2n 次比较...

min=max=infile.nextInt();
while ( infile.hasNextInt() )
    {

        int placeholder = infile.nextInt(); // works as a placeholders
        if (placeholder < min)
        {
            min = placeholder;
        }
        if (placeholder > max)
        {
            max = placeholder;

注意:我只能更改 while 循环中的内容。我只是不知道如何使用基本的 for 循环轻松找到最小值和最大值...对此有任何简单的解决方案吗？我错过了什么？

Answer 1

我不认为你可以在 n 比较中做到这一点。您可以按以下方式进行 3n/2 - 2 比较:

1. 将元素成对取出并比较每对中的元素。将每次比较的较高值放在一个列表中，将较低的值放在另一个列表中。这需要进行 n/2 次比较。
2. 从较高值列表中找出最大值:n/2-1 次比较。
3. 从较低值列表中找到最小值:n/2-1 次比较。