查找哪个矩阵行具有最高和java

Question

我正在尝试编写一个递归非静态方法，该方法对于每个给定矩阵将返回具有最高总和的行号。我不允许使用静态方法和 for 循环（在我编写的任何方法中）。我认为解决方案是使用三种方法：(private) 计算给定行的总和。（私人）比较行的总和与使用方法＃1i的总和i+1（公共）检查矩阵是否有多于一行并在行上应用#2 0。我觉得我用我解决这个问题的方式把事情复杂化了。如果有人愿意向我建议更好的算法，我会很乐意尝试。无论如何，我相信我对#1 和#3 没问题。我的问题是#2。我不知道如何设置行号变量：public class Matrix {private int[][] _mat;public Matrix(int sizeRow, int sizeCol) {   _mat = new int[sizeRow][sizeCol];}private int maxRow(int row) { //Recursive method #2: comparing sum of i and i+1        int rowNumber;        if (row <= _mat.length) {            if (rowSum(row, 0) > rowSum(row+1,0)) {                rowNumber = row;                return maxRow(row+1);            }            else {                return rowNumber;            }        }        else {            return rowNumber;        }    }..public int maxRow() {..} //Recursive method #3private int rowSum(int i, int j) {..} //Recursive method #1}我的问题是 var rowNumber。它还没有被初始化，如果我要初始化它，它将被设置为0每次我调用该方法时。

Answer 1

如果需要返回总和最大的行的索引，可以这样做：

private int maxRow(int current_index, int max_index) {

    if (current_index == _mat.length) {

        return max_index;

    } else if (sumRow(current_index) > sumRow(max_index)) {

        return maxRow(current_index+1, current_index);

    } else {

        return maxRow(current_index+1, max_index);

    }

}

maxRow(1, 0); //method call

第一个参数current_index存储您当前正在测试的索引，而参数max_index存储到目前为止访问过的具有最大总和的索引。

第一个子句确保您在到达数组末尾时返回具有最大总和值的任何索引。

max_index一旦找到总和高于之前的行，第二个子句就会更新。

当上述情况没有发生时，第三个子句只是迭代到下一行。

您可以调用该方法current_index=1，max_index=0因此您不需要max_index使用无效值进行初始化。

如果你想提高性能，你还可以添加一个新的参数max_value来存储当前的最大和，这样你就不需要在每次递归调用时都调用它。

Answer 2

这是一个示例，说明如何检索总和最高的行的索引。

public class MaxRowFromArray {

    private final int[][] values;

    public MaxRowFromArray(int[][] values) {

        this.values = values;

    }

    private int sumOfRow(int[] row, int rowIndex, int sum) {

        if (rowIndex > row.length - 1) {

            return sum;

        }

        return sumOfRow(row, rowIndex + 1, sum + row[rowIndex]);

    }

    private int highestRow(int column, int highestIndex, int highestRow) {

        if (column > values.length - 1) {

            return highestIndex;

        }

        int sumOfRow = sumOfRow(values[column], 0, 0);

        if (sumOfRow > highestRow) {

            return highestRow(column + 1, column, sumOfRow);

        }

        return highestRow(column + 1, highestIndex, highestRow);

    }

    public int highestRow() {

        int highest = highestRow(0, 0, -1);

        if (highest == -1) {

            throw new IllegalStateException("No row can be found with the highest sum.");

        }

        return highest;

    }

}

测试

    public static void main(String[] args) {

        MaxRowFromArray max = new MaxRowFromArray(new int[][] {

                { 1 },

                { 1, 2 },

                { 1, 2, 3 },

                { 1, 2, 3, 4}

        });

        int expectedHighest = 3;

        int highestIndex = max.highestRow();

        if (highestIndex != expectedHighest) {

            throw new AssertionError(String.format("Highest index %s was not the expected highest %s.",

                    highestIndex, expectedHighest));

        }

        System.out.println("Highest: " + highestIndex);

    }