数组中最大数之和

huangapple go评论112阅读模式
英文:

sum of Max numbers in Array

问题

static void miniMaxSum(int[] arr) 
{
    Arrays.sort(arr);
    Integer min = arr[0] + arr[1] + arr[2] + arr[3];
    Integer max = arr[4] + arr[3] + arr[2] + arr[1];
    System.out.println(min + " " + max);
}
英文:

arr is an int array of 5 elements only.
We need to calculate sum of only 4 smallest minimum numbers and sum of 4 largest maximum mumbers from these 5 elements.

example: int[] arr= {5,2,3,4,1}

In this array,
4 smallest minimum numbers are: 1,2,3,4 so totalMin = 1 + 2 + 3 + 4 = 10

Largest 4 Maximum numbers are: 5,4,3,2 so totalMax = 14

So output will be : 10, 14.

My below code is working correctly for 40% cases, but not working for 60% cases.

I sorted Array first .. so that always smallest numbers will be: arr[0], arr[1], arr[2], arr[3] and MAX will be arr[4], arr[3], arr[2], arr[1]

HackerRank showing that my this answer is wrong for some cases , but those are locked. I dont know those cases... I am also wondering what will be those cases?

Can anybody explain me? What wrong am doing here?

You can check more details of question here: https://www.hackerrank.com/challenges/mini-max-sum/problem

static void miniMaxSum(int[] arr) 
{
    Arrays.sort(arr);
    Integer min=arr[0]+arr[1]+arr[2]+arr[3];
    Integer Max=arr[4]+arr[3]+arr[2]+arr[1];
    System.out.println(min+" "+Max);
}

答案1

得分: 6

根据给定的约束条件,您可以产生的最大和是 4 * 10^9,这会导致整数溢出。然而,它可以很好地适应 long 类型,所以将值作为 long 类型相加应该就可以解决问题:

long min = (long)arr[0] + (long)arr[1] + (long)arr[2] + (long)arr[3];
long max = (long)arr[4] + (long)arr[3] + (long)arr[2] + (long)arr[1];

但需要注意的是,这种解决方案仍然具有 O(nlog(n)) 的时间复杂度,因为涉及到排序。
可以将其改进为 O(n) 的复杂度 - 在对数组进行单次遍历时,您可以得到它的总和、最小值和最大值,然后从总和中减去最大值以获得“最小”值,并从总和中减去最小值以获得“最大”值。

使用 IntStream 可以为您完成大部分的重 lifting:

IntSummaryStatistics stat =  Arrays.stream(arr).summaryStatistics();
long min = stat.getSum() - stat.getMax();
long max = stat.getSum() - stat.getMin();
英文:

With the given constraints, the largest sum you can produce is 4 * 10<sup>9</sup>, which overflows an integer. However, it fits nicely into a long, so summing the values as longs should do the trick:

long min = (long)arr[0] + (long)arr[1] + (long)arr[2] + (long)arr[3];
long max = (long)arr[4] + (long)arr[3] + (long)arr[2] + (long)arr[1];

Note, however, that this solution still has an O(nlog(n)) time complexity due to the sorting.<br/>
This can be improved to O(n) - in a single pass of the array you could get the sum, min and max of it, and then subtract the maximum from the sum to git the "min" value and the minimum from the sum to get the "max" value.

Using an IntStream will do most of the heavy lifting for you:

IntSummaryStatistics stat =  Arrays.stream(arr).summaryStatistics();
long min = stat.getSum() - stat.getMax();
long max = stat.getSum() - stat.getMin();

答案2

得分: 1

first = arr[0]

second = arr[1]

third = arr[2]

fourth = arr[3]

fifth = arr[4]

min_sum = first + second + third + fourth

max_sum = second + third + fourth + fifth

# 上述代码将起作用,原因是输入和结果可能超过32位,所以我们必须使用 long 类型,
# 在执行求和操作之前,我们需要将每个 long 值都进行类型转换,
# 因为其结果也可能超过32位。
英文:
long first =  arr[0];

long second =  arr[1];

long third =  arr[2];

long fourth =  arr[3];

long fifth =  arr[4];

long min = first + second + third + fourth;

long Max  = second + third + fourth + fifth;

Above will work, the reason being is input and result may exceed 32 bit so we have to use long and we have cast each value of long before doing the sum operation because, it may also exceed more than 32 bit

答案3

得分: 0

是的。我的错误,没有将int转换为long(64位整数)。错误是因为整数溢出

static void miniMaxSum(int[] arr) 
{
    Arrays.sort(arr);
    long min = (long)arr[0] + (long)arr[1] + (long)arr[2] + (long)arr[3];
    long max = (long)arr[4] + (long)arr[3] + (long)arr[2] + (long)arr[1];
    System.out.println(min + " " + max);
}
英文:

Yes. My mistake, was not converting int to long (64-bit Integer).Error was because of integer Overflow

    static void miniMaxSum(int[] arr) 
     {
        Arrays.sort(arr);
        long min= (long)arr[0]+(long)arr[1]+(long)arr[2]+(long)arr[3];
        long max= (long)arr[4]+(long)arr[3]+(long)arr[2]+(long)arr[1];
        System.out .println(min+&quot; &quot;+max);
     }

huangapple
  • 本文由 发表于 2020年9月8日 17:58:57
  • 转载请务必保留本文链接:https://go.coder-hub.com/63791520.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定