Java中打印最大值和最小值

Question

我最近开始在 HackerRank 上练习，以提高我的编码技能，主要使用 Java 作为我的首选语言。我有一个问题，我已经尽力给出了解决方案，但没有通过所有的测试用例。我只通过了 15 个测试用例中的 5 个，还剩下 10 个测试用例未完成。在 HackerRank 上的用户可以通过此链接查看问题: Min-Max Sum 问题简述如下：

问题陈述：

给定五个正整数，找到仅对其中四个整数进行求和所能得到的最小值和最大值。然后将分别计算出的最小值和最大值作为两个长整型数并在单行中输出，两个数之间用一个空格隔开。

例如，arr=[1,3,5,7,9]。我们最小的总和是1+3+5+7=16，我们最大的总和是3+5+7+9=24。我们应该打印16 24 输出格式：

打印两个用空格分隔的长整型数，表示可以通过将恰好四个整数相加计算出的分别最小和最大的值。（输出可以大于32位整数。） 示例输入 1 2 3 4 5 示例输出 10 14 解释： 我们的起始数字是1、2、3、4 和 5。我们可以使用其中四个数字计算出以下几个总和：

If we sum everything except 1, our sum is 2+3+4+5=14.
If we sum everything except 2, our sum is 1+3+4+5=13.
If we sum everything except 3, our sum is 1+2+4+5=12.
If we sum everything except 4, our sum is 1+2+3+5=11.
If we sum everything except 5, our sum is 1+2+3+4=10.

我的算法

  for(i=0; i<arr.length; i++){
    totSum += arr[i];
  }

  sumOne = totSum - arr[0];
  sumTwo = totSum - arr[1];
  sumThree = totSum - arr[2];
  sumFour = totSum - arr[3];
  sumFive = totSum - arr[4];

  int[] num = {sumOne, sumTwo, sumThree, sumFour, sumFive};
  int temp = 0;
  for(i=0;i<num.length;i++){
    for(int j=1;j<(num.length-i);j++){
        if(num[j-1] > num[j]){  
            //swap elements  
            temp = num[j-1];  
            num[j-1] = num[j];  
            num[j] = temp;  
        }
    }
  }

  System.out.print(num[0] + " " + num[4]);

我们也可以通过迭代`num array`，找到最大值和最小值来实现这一点。

但是不知道为什么，我还是没能通过这个模块。

请注意：arr中的元素数量是固定的，只有5个。

我已经了解到，在这10个失败的测试用例中，其中一个测试用例如下：

输入(stdin) 256741038 623958417 467905213 714532089 938071625

期望输出 2063136757 2744467344

- Alok

---

你需要什么样的帮助？ - Phenomenal One

我正在努力弄清楚为什么我的代码在其余的10个案例中失败了@MaruthiAdithya。由于您知道我们无法看到所有测试用例的结果，因此我已添加了一个输入引发了一个查询，并使我的代码失败。请看最后一行。 - Alok

@Alok 将 int 改为 long int 或尝试 long long int。 - Phenomenal One

但是你不觉得排序也会给出我的答案吗？因为在打印中，我已经将第一个元素作为最小值，而最后一个元素是最大值。@NomanKhan 没有任何区别。 - Alok

Answer 1

您的想法没错（尽管对数组进行排序有点过度，因为您只需要其最大值和最小值），但是当您对这些大整数求和时，会导致 sumtot 变量 溢出 并得到错误答案。使用 long 应该可以解决这个问题：

long totSum = 0;
for(int i=0; i<arr.length; i++){
    totSum += arr[i];
}

long sumOne = totSum - arr[0];
long sumTwo = totSum - arr[1];
long sumThree = totSum - arr[2];
long sumFour = totSum - arr[3];
long sumFive = totSum - arr[4];

long[] num = {sumOne, sumTwo, sumThree, sumFour, sumFive};
long temp = 0;
for(int i=0;i<num.length;i++){
    for(int j=1;j<(num.length-i);j++){
        if(num[j-1] > num[j]){
            //swap elements
            temp = num[j-1];
            num[j-1] = num[j];
            num[j] = temp;
        }
    }
}

System.out.print(num[0] + " " + num[4]);

请注意，顺便提一下，使用Java 8的流可以实现相同的逻辑，并节省大量样板代码和O(nlog(n))排序。

IntSummaryStatistics stats = Arrays.stream(arr).summaryStatistics();

System.out.println
    ((stats.getSum() - stats.getMax()) + " " + (stats.getSum() - stats.getMin()));

- Mureinik

Answer 2

首先，您需要使用long，因为值的总和可能会超出整数最大值。 然后，您不需要双重循环，可能由于此原因未通过某些性能测试用例。请参见此解决方案，它为2N解决方案提供了2个分离的循环。

package minmaxsum;

public class MinMaxSum {
  public static void main(String[] args) {
    MinMaxSum mms = new MinMaxSum();
    mms.printMinMaxSum(new int[] {256741038, 623958417, 467905213, 714532089, 938071625});

    // mms.printMinMaxSum(new int[] {1, 3, 5, 7, 9});
  }

  public void printMinMaxSum(int[] arr) {
    long totalSum = 0;
    for (int num : arr) {
      totalSum += num;
    }

    long min = Long.MAX_VALUE;
    long max = Long.MIN_VALUE;

    for (int num : arr) {
      long currentSum = totalSum - num;

      min = Math.min(min, currentSum);
      max = Math.max(max, currentSum);
    }

    System.out.println(min + " " + max);
  }
}

- fpezzini

---

嘿，我不知怎么的理解了你的代码，但我想问一个问题，在第二个循环开始时，min和max变量中输入的值是什么，或者让我知道这个min = Long.MAX_VALUE和max = Long.MIN_VALUE是如何有意义的？谢谢。 - Alok

min从long变量的最大可能值开始。这样，当它与任何其他数字进行比较时，如50L，它将保证被该值替换。这个想法是我们将通过值循环并适当地设置min和max。 - fpezzini

Answer 3

这适用于所有测试案例。刚刚提交了代码。

 static void miniMaxSum(int[] arr) {
         Arrays.sort(arr);
            long minSum=0,maxSum=0;
            for(int i=0;i<4;i++){
               minSum+=arr[i];
               maxSum+=arr[arr.length-1-i] ;
            }
            System.out.println(minSum + " " + maxSum);

    }

并非所有测试用例都具有排序数据。 一旦数组排序，单个循环就足以计算最小和最大值之和。 排序有助于将时间复杂度从O(n*n)降低到O(nlogn)

- Noman Khan

---

我已经尝试按照我的方式去做，即“循环到arr.length”，但它给了我错误的答案。为什么会这样呢？所以根据陈述，我理解minSum是除最大数外所有数的总和，maxSum则相反。因此，我所做的是循环到arr.length，并初始化minsum += arr[i]和maxSum += arr[i+1]。它抛出了arrayoutofboundexception异常。由于排序数组包含从右到左排序的元素。你能帮我解决这个问题吗？ - Alok

预期输出是4个元素的总和。从0到arr.length-1的循环将导致5个数字的总和，因此答案错误。此外，如果您从0到arr.length循环，那么当i的值达到array.length-1时，maxSum += arr[i+1]将导致数组越界。 - Noman Khan

我已经找到了方法，并且也理解了你的意思，但是我简化了最大值求和的步骤，只需循环遍历数组直到 arr.length-1，即可得到 minSum += arr[i]，然而我们实际上不需要按照你建议的 arr[arr.length-1-i] 的步骤来计算 maxSum。maxsum += arr[i+1] 也可以完成任务。 - Alok

Answer 4

需要改变思考方式：作为程序员，通常最好像机器一样思考，而不是像人类一样。

问问自己，如果有一个元素不在数组中，那么最大值是多少？答案是除了最大值元素以外的所有元素之和。因此，如果你只是找到具有最大值的元素，并对其余元素求和，这就是解决问题的第一部分。同样的逻辑也适用于minimumSum...

这种思考方式可以减少解决问题所需的时间和精力。

例如，在一个循环中找到最大元素和最小元素。

在第二个循环中，将两个结果相加 - sumMax += array[index] 避免使用最大元素的索引; sumMin += array[index] 避免使用最小元素的索引。

当然，以上所有内容都可以在一个循环中完成，但由于这是提高编程技能的任务，我会留给你（以及编写代码）。

- zlakad

Answer 5

这里是解决这个问题的算法。

算法-

步骤1 我们将在数组中找到最小元素。

步骤2 我们将在数组中找到最大元素。

步骤3 我们将计算数组中所有元素的总和。

步骤4 我们通过从数组中的总和中减去最大值来计算minsum。

步骤5 我们通过从整体总和中减去最小值来计算maxsum。

最后，我们将打印minsum和maxsum。

这是该算法的实现。

static void miniMaxSum(int[] arr) {
        long min = 0, max = 0, sum = 0;
        min = arr[0];
        max = min;
        sum = min;
        for (int i = 1; i < arr.length; i++) {
            sum += arr[i];
            if (arr[i] < min) {
                min = arr[i];
            }
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        System.out.print((sum - max) + " " + (sum - min));

    }

希望这可以帮到你。如果你需要更多解释，你可以参考这个tutorial。

- Kanahaiya