查找每行和每列中第二大数字的总和

Question

二维数组中的每个元素都被认为是一块巧克力。除了每行和每列的最大巧克力之外，我需要选择最大数量的巧克力。我做了一个程序，但它没有为下面提到的例子产生正确的结果。1 4 0 5 2 | 42 1 2 0 1 | 10 2 3 4 4 | 30 3 0 3 1 | 11 2 2 1 1 | 1列： 1+3+2+4+2=12行： 4+1+3+1+1=10全部的： 12+10=22输出应该是 22，但我下面附加程序的输出是 20。public int calc(int[][] grid, int rows, int columns){    int[][] check = new int[rows][columns];    int max, pos;    for(int i=0; i<rows; i++){        max = grid[i][0];        pos = 0;        for(int j=0; j<columns; j++){            if(grid[i][j] >= max){                max = grid[i][j];                pos = j;            }        }        check[i][pos] = 1;    }    for(int j=0; j<columns; j++){        max = grid[0][j];        pos = 0;        for(int i=0; i<rows; i++){            if(grid[i][j] >= max){                max = grid[i][j];                pos = i;            }        }        check[pos][j] = 1;    }    int total = 0;    for(int i=0; i<rows; i++){        for(int j=0; j<columns; j++){            if(check[i][j]!=1){                total += grid[i][j];            }        }    }    return total;}

Answer 1

您的应用程序没有考虑到maxin a column 和maxin a row 可能是同一个元素（或者不是，可选）。例如，第 1 行有2 1 2 0 1. 第一个2是第max0 列的 ，但两者2都是第 1 行的最大值。您的应用程序将第2一个标记为max第二个循环中的列，将第二个标记为第一个循环2中的一行max。

请注意，类似的情况存在于具有 value 的第二行中4，但在这种情况下，您的应用程序仅将4's标记为最大值（因为您正在>= max两个循环中进行检查。如果您只检查，> max则2's 将在第 1 行中是正确的，但您的4's 会在第 2 行中搞砸）。

如果您的示例肯定应该返回 22，那么您需要添加逻辑来检查max行和列上的值的交集。

下面是一个蛮力更新，它保留了您的大部分逻辑/结构。我更新了check数组以保留找到的最大值，而不仅仅是 a 1，并添加了一个额外的嵌套循环，用于检查每一行的max值是否相等。在最后一个循环中，我更新了对!=1to的检查==0。

static public int calc(int[][] grid, int rows, int columns){

int[][] check = new int[rows][columns];

int max, pos;

for(int i=0; i<rows; i++){

    max = grid[i][0];

    pos = 0;

    for(int j=0; j<columns; j++){

        if(grid[i][j] >= max){

            max = grid[i][j];

            pos = j;

        }

    }

    check[i][pos] = max; // updated here

}

for(int j=0; j<columns; j++){

    max = grid[0][j];

    pos = 0;

    for(int i=0; i<rows; i++){

        if(grid[i][j] >= max){

            max = grid[i][j];

            pos = i;

        }

    }

    check[pos][j] = max; // updated here

}

// UPDATE HERE

// these loops look for rows that have two 

// max values (one for a column and one for a row) that are equal

for(int j=0; j<rows; j++){

  max = 0;

  for(int i=0; i<columns; i++){

    if(check[j][i] != 0) {

      if (max == 0){

        max = check[j][i];

      }else if (max == check[j][i]){

        // reset

        check[j][i] = 0;

      }

    }

  }

}

int total = 0;

for(int i=0; i<rows; i++){

    for(int j=0; j<columns; j++){

        if(check[i][j]==0){ // updated here

            total += grid[i][j];

        }

    }

}

return total;

}