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

Question

我需要实现 method/function 以确定矩阵中是否存在数字。给定的矩阵按行和列的降序排序。这里有定义矩阵的三个例子：

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 的列中搜索数字，然后继续查找其余列（但我不知道如何在我的代码中实现它）。

我的代码如下，但是当运行ning 时，这个错误不断弹出 java.lang.WhosebugError.I 明白我正在使缓冲区的内存饱和，但我不需要修改它来实现功能工作。我想避免它，除非它是唯一的解决方案。

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

我认为以下 link 分析了您尝试使用代码示例和复杂性分析所做的事情：

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

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

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

Use Divide and Conquer for find a number into matrix sorted

java

algorithm

divide-and-conquer