java - 查找数组中最小值和最大值的有效方法

Question

我想找出整数数组中的最小值和最大值。

以下哪一种方式效率更高？

1. 对数组进行排序，然后查看开始和结束以获取最小值和最大值。

2. 使用 Arrays.asList() 将数组转换为列表，然后使用 Collections.min() 方法。

我想使用它的代码如下:

// Find missing number from an array of consecutive numbers arranged randomly
import java.util.Arrays;

public class MissingNumber {

    public static void main(String[] args) {

        int[] consecutiveRandomNos = { 3, 6, 5 };

        System.out.println(addNumbers(consecutiveRandomNos));
        System.out.println("The missing number is "
                        + (returnSum(consecutiveRandomNos) - addNumbers(consecutiveRandomNos)));
    }

    public static int addNumbers(int... numbers) {
        int result = 0;

        for (int number : numbers) {
            result += number;
        }

        return result;
    }

    public static int returnSum(int... nos) {

        Arrays.sort(nos);

        int max = nos[nos.length - 1];

        int min = nos[0];

        int total = 0;

        for (int i = min; i <= max; i++) {
            total += i;
        }

        return total;
    }
}

Answer 1

排序最多为 O(Nlog(N))。只需迭代数组，您就可以在 O(n) 中轻松找到最小值和最大值。

int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for(int i=0; i<array.length; i++)
{
    if(array[i] < min)
       min = array[i]
    if(array[i] > max)
       max = array[i]
}

编辑:

<小时/>

我注意到您粘贴了一些额外的代码，并且您实际上想在连续数字数组中找到丢失的数字。无需迭代那么多，而是 mathematical summations这可以在 O(1) 时间内帮助你。事实上，您可以通过单个 for 循环解决整个问题:

int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
int sum = 0;
for(int i=0; i<array.length; i++)
{
    if(array[i] < min)
       min = array[i];
    if(array[i] > max)
       max = array[i];
    sum += array[i];
}

return (max - min + 1)(max + min)/2 - sum;