如何只进行“n”比较，从文本文件中查找最小值和最大值？

Question

所以我有一个文件，里面有n个整数。在找到min和max而不是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循环轻松找到min和max ...这有什么简单的解决方案吗？我错过了什么？

Answer 1

我不认为你可以在n比较中做到这一点。您可以在3n / 2 - 2比较中进行如下操作：

1. 成对拍摄物品并比较每对中的物品。将每个比较中的较高值放在一个列表中，将较低值放在另一个列表中。这需要n / 2次比较。
2. 从较高值列表中查找最大值：n / 2-1比较。
3. 从较低值列表中找出最小值：n / 2-1比较。

Answer 2

正如MadPhysicist所说：你可以将两个if改为if / else if：

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

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

在最好的情况下（严格递减的序列，每个值都小于前一个），您只需要n-1比较。

在最坏的情况下（严格增加的序列，其中每个值都大于前一个值），您仍然需要2*(n-1)比较。您无法完全消除这种情况：如果某个值大于当前最小值，则可能是新的最大值。

典型的情况（随机的值序列）你需要在n-1和2*(n-1)比较之间的东西。

另请注意，我将最小值的比较从<更改为<=：如果值等于最小值，则它不能同时为新的最大值。

Answer 3

我认为你的方法是最优的，因为它需要进行O（n）比较。根据Big O，n或2n并不重要：

int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;

while (infile.hasNextInt()) {
    int val = infile.nextInt();

    if(val < min)
        min = val;
    else if(val > max)
        max = val;
}

您可以使用额外的存储来执行相同的操作，但在这种情况下，您可以减少比较，但需要额外的空间：

TreeSet<Integer> unique = new TreeSet<>();

while(infile.hasNextInt())
    unique.add(infile.nextInt());

int min = unique.pollFirst();
int max = unique.pollLast();

Answer 4

鉴于您将min / max初始化为第一个元素，您可以进行2(n - 1)比较。此外，如果您将两个ifs更改为if-else if，您将至少保存一个比较，总共2n - 3。

因此，@Matt Timmermans' answer的概括是可能的：

将您的输入拆分为大小为k的组。使用2k - 3比较找出每组的最大值和最小值。这将留下n/k项目来检查最小值和n/k项目来检查最大值。您有两种选择：

1. 只需进行比较，共计(n/k) * (2k - 3) + 2 * (n/k - 1)。这表明Matt的答案是最优的，因为k = 2的表达式最小（对于k的所有值，该分数减少到n以上）。
2. 继续分成大小为k（或其他一些大小）的组。找到k元素的最大值需要k-1比较。所以你可以再次将你的n/k最小候选人分成k组，以获得n/k2候选人进行额外的n/k * (k-1)比较。你可以继续这个过程去获得总共(n/k) * (2k - 3) + 2 * (k - 1) * Σ n/ki。总和evaluates to 1 / (k-1)，所以总数是> 2n，甚至补偿了总和中隐含的挥手过度近似。

方法＃2不减少比较次数的原因在于，对于每个标准，将列表分成两组候选者将获得最大的收益。计算的其余部分最好通过单个遍历每个列表进行优化。

这个故事的寓意是，虽然你可以在这里和那里保存几个比较，但你可能不应该这样做。您必须考虑设置其他列表（甚至进行就地交换）所产生的开销，以及代码的易读性以及其他因素。