查找最小和使用1.5n比较得出数组中的最大值 [英] Find Min & Max in an Array using 1.5n comparisons

问题描述

我正尝试在下面的代码中找出如何计算比较次数，有没有办法在代码中执行此操作?

I'm trying to figure out in the code below how to count the number of comparisons that are made, is there a way to do this in code?

也在 for循环中，它如何迭代到 a.length-1 而不是 a.length

Also in the for loop how come it iterates up to a.length - 1 and not a.length

public static void minmax1(int[] a) {

    if (a == null || a.length < 1)
        return;

    int min, max;

    // if only one element
    if (a.length == 1) {
        max = a[0];
        min = a[0];
        System.out.println("min: " + min + "\nmax: " + max);
        return;
    }

    if (a[0] > a[1]) {
        max = a[0];
        min = a[1];
    } else {
        max = a[1];
        min = a[0];
    }

    for (int i = 2; i <= a.length - 1; i++) {
        if (max < a[i]) {
            max = a[i];
        } else if (min > a[i]) {
            min = a[i];
        }
    }

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

推荐答案

如何计算进行比较的次数?

how to count the number of comparisons that are made?

您添加一个计数器变量，然后在每次进行值比较时将其递增，如下所示:

You add a counter variable, then increment it every time you make a value comparison, like this:

public static void minmax1(int[] a) {

    if (a == null || a.length < 1)
        return;

    int min, max, count = 0;                       // added comparison counter

    // if only one element
    if (a.length == 1) {
        max = a[0];
        min = a[0];
        System.out.println("min: " + min + "\nmax: " + max);
        return;
    }

    count++;                                       // comparison on next line
    if (a[0] > a[1]) {
        max = a[0];
        min = a[1];
    } else {
        max = a[1];
        min = a[0];
    }

    for (int i = 2; i <= a.length - 1; i++) {
        if (max < a[i]) {
            count++;                               // 1 comparison to get here
            max = a[i];
        } else if (min > a[i]) {
            count += 2;                            // 2 comparisons to get here
            min = a[i];
        } else {
            count += 2;                            // 2 comparisons to get here
        }
    }

    System.out.println("min: " + min + "\nmax: " + max);
    System.out.println("comparisons: " + count);   // print comparison counter
}

这篇关于查找最小和使用1.5n比较得出数组中的最大值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！