java - 使用分而治之找到一个数字到矩阵排序

Question

我需要实现一种方法/函数来确定矩阵中是否存在数字。给定的矩阵按行和列的降序排序。这里有定义矩阵的三个例子:

private static int[][] matrix1= {

    {69, 57, 43, 28, 14},
    {68, 56, 35, 25, 13},
    {66, 55, 34, 22, 8},
    {64, 52, 32, 21, 7},
    {62, 47, 31, 17, 5}
};

private static int[][] matrix2 = {
    {62, 47, 31, 17, 5}
};

private static int[][] matrix3 = {
    {14},
    {13},
    {9},
    {7},
    {5}
};

函数，应该遵循分而治之的原则。我的想法是寻找一个矩阵的元素作为枢轴，并从中划分矩阵。如果我们要查找的数字大于主元，我们将保留主元左侧的列和它自己的列，但保留主元的前几行。如果枢轴较大，则相反(下一列和它自己的下行)。此外，为了优化代码，首先我需要在 pivot 的列中搜索数字，然后继续查找其余列(但我不知道如何实现这个在我的代码中)。

我的代码如下，但是在运行时，这个错误不断弹出 java.lang.StackOverflowError。我知道我正在使缓冲区的内存饱和，但我不需要修改它来使函数工作。我想避免它，除非它是唯一的解决方案。

public boolean contains(int[][] matrix, int num) {
    int rowMin = 0;
    int rowMax = matrix.length-1;
    int colMin = 0;
    int colMax = matrix[0].length-1; 
    return containsAux(matrix, rowMin, colMin, rowMax, colMax, num);

}
private boolean containsAux(int[][]matrix, int rowMin, int colMin, int rowMax, int colMax, int num) {
    boolean resul=false;
    int col= (colMax+colMin)/2;
    int row=(rowMax+rowMin)/2;
    int pivote= matrix[row][col];

    if(pivote==num) {
        resul=true;
    }else if(pivote<num && rowMin>=0 && colMin>=0) {
        containsAux(matrix,row-1,col,rowMin,col,num);
        containsAux(matrix,row-1,col-1,rowMin,col-1,num);
        fila-=1;
        containsAux(matrix,row+1,col-1,rowMax,col-1,num);
    }else if (pivote> num && rowMax<matrix.length && rowMax<matrix[0].length) {
        containsAux(matrix,row+1,col,rowMax,col,num);
        rowMin-=1;
        containsAux(matrix,rowMin+1,col+1,row,col+1,num);
        containsAux(matrix,row+1,col+1,rowMax,col+1,num);
    }

    return resul;
}

我的测试代码是:

public class Prueba {

    private static int[][] matrix = {
        {69, 57, 43, 28, 14},
        {68, 56, 35, 25, 13},
        {66, 55, 34, 22, 8},
        {64, 52, 32, 21, 7},
        {62, 47, 31, 17, 5}
    };

    public static void main(String[] args) {
        CartonBingo cb= new CartonBingo();

        System.out.println(cb.contains(matrix, 35));
    }
}

我的问题是:是否有另一种方法可以遵循分而治之的原则来做到这一点，或者我应该更改代码以使其顺利运行？提前谢谢你。

Answer 1

我认为以下链接分析了您尝试使用代码示例和复杂性分析进行的操作:

http://www.geeksforgeeks.org/divide-conquer-set-6-search-row-wise-column-wise-sorted-2d-array/

无论如何，我认为您的代码中有一些错误，更新递归调用中的参数或类似的东西。程序继续对函数执行相同的调用，直到发生 stackoverflow。