java - 优化代码以查找矩阵中直线(行、列或对角线)中的最大连续点

Question

我需要找到矩阵中直线(行、列或对角线)中连续点的最大数量。

例如:- 如果它是一个 4*4 矩阵 输入是 (1#1,2#2,3#3,2#1) 答案应该是 3，因为对角线上的最大连续点是 3。

我的代码已成功执行并获得预期结果。但是代码复杂度非常高。

有人可以建议复杂性方面的最佳方法吗。

下面是我的代码:

// Get the max number of Continuous points in a matrix row
private static int getMaxContinuousPointsInRow(boolean[][] matrix, int row){
    int maxCount = 0;
    int currCount = 0;
    int pos = 0;
    while(pos < matrix[row].length){
        currCount = 0;
    while(pos < matrix[row].length && !matrix[row][pos])
        pos++;
    if(pos >= matrix[row].length)
        break;
    while(pos < matrix[row].length && matrix[row][pos]){
        currCount++;
        pos++;
    }
    if(currCount > maxCount)
        maxCount = currCount;
    }
    return maxCount;
}

// Get the max number of Continuous points in a matrix row
private static int getMaxContinuousPointsInCol(boolean[][] matrix, int col) {
    int maxCount = 0;
    int currCount = 0;
    int pos = 0;

    while (pos < matrix.length) {
        currCount = 0;
    while (pos < matrix.length && !matrix[pos][col])
        pos++;
    if(pos >= matrix.length)
        break;
    while (pos < matrix.length && matrix[pos][col]) {
        currCount++;
        pos++;
    }
    if (currCount > maxCount)
        maxCount = currCount;
    }
    return maxCount;
}

// Get the max number of Continuous points in a matrix diagonal right starting from position (row,col)
private static int getMaxContinuousPointsInDiagonalRight(boolean[][] matrix, int row, int col) {
    int maxCount = 0;
    int currCount = 0;
    int i = row, j = col;
    while (i < matrix.length && j < matrix[row].length) {
        currCount = 0;
    while (i < matrix.length && j < matrix[row].length && !matrix[i][j]){
        i++;
        j++;
    }
    if(i >= matrix.length || j >= matrix[row].length)
        break;
    while (i < matrix.length && j < matrix[row].length && matrix[i][j]) {
        currCount++;
        i++;
        j++;
    }
    if (currCount > maxCount)
        maxCount = currCount;
    }
    return maxCount;
}

public static int function_called_by_main_method(int input1, int input2, String[] input3) {
    // create a boolean matrix of size  input1 x input2
    // M[i][j] = true if  input3 contains a point i#j, else M[i][j] = false
    boolean M[][] = new boolean[input1 + 1][input2 + 1];
    // initialize the matrix with all false values
    for(int i=0; i <= input1; i++){
        for(int j=0; j <= input2; j++){
            M[i][j] = false;
        }
    }
    // process each value in input3 and populate the matrix
    for (String s : input3) {
        // extract row, column value
        String[] data = s.split("#");
        int i = Integer.parseInt(data[0]);
        int j = Integer.parseInt(data[1]);
        M[i][j] = true;
    }
    // get max number of Continuous points among all matrix rows
    int max = 0;
    for(int row = 0; row <= input1; row++){
        int rowMax = getMaxContinuousPointsInRow(M, row);
        if(rowMax > max)
        max = rowMax;
    }
    // get max number of Continuous points among all matrix rows and columns
    for (int col = 0; col <= input2; col++) {
        int colMax = getMaxContinuousPointsInCol(M, col);
        if (colMax > max)
        max = colMax;
    }
    // get max number of Continuous points among all matrix rows, columns and right diagonals
    for(int col = input2 ; col >= 0; col--){
        int diagMax = getMaxContinuousPointsInDiagonalRight(M, 0, col);
        if(diagMax > max)
        max = diagMax;
    }
    for(int row = 1 ; row <= input1; row++){
        int diagMax = getMaxContinuousPointsInDiagonalRight(M, row, 0);
        if(diagMax > max)
            max = diagMax;
    }
    return max;
}

Answer 1

您可以尝试使用 Java 8 流进行并行处理，采用一种愚蠢的蛮力方法。

class Coord {
    int i;
    int j;
}

List<Coord[]> allLineCoords = calculateLinesForMatrix(rows, columns);

Comparator<Coord[]> comparator = (coords1, coords2) ->
        length(matrix, coords1) - length(matrix, coords2);

Coord[] maxCoords = allLineCoords.parallelStream()
    .max(comparator);

// or for just the max length:

int maxLength = (int) allLineCoords.parallelStream()
    .mapToInt(coords -> length(matrix, coords))
    .max();

非常不满意的是缺少情报。并行性仅与计算机的核心数量成比例。