如何在2D阵列中找到局部最小值?

时间:2021-05-27 19:36:20
public static void main(String[] args) {
    // TODO code application logic here
    int numRows = 5;
    int numCols = numRows;
    int[][] twoDimArray = new int[numRows][numCols];
    Random randGen = new Random();

    for (int i = 0; i < numRows; i++) {
        for (int j = 0; j < numCols; j++) {
            int randIndex = randGen.nextInt(4);
            int value = randGen.nextInt(100);
            twoDimArray[i][j] = value;
        }
    }
    System.out.println("\nThe two-dimensional array: ");
    for (int i = 0; i < numRows; i++) {
        for (int j = 0; j < numCols; j++) {
            System.out.print(twoDimArray[i][j] + " ");
        }
        System.out.println();

    }  
    }
}

I want to find a local minimum using a "brute force" approach. I know with a one dimensional array I would use a for-loop to compare all the elements in the array until I found a local minimum, but I don't know how to do that here.

我想找到一个使用“强力”方法的局部最小值。我知道使用一维数组我会使用for循环来比较数组中的所有元素,直到找到局部最小值,但我不知道如何在这里做。

Edit: Could I use binary search instead? Find the middle row and search there and if one isn't found, I search one of the halves.

编辑:我可以使用二进制搜索吗?找到中间行并在那里搜索,如果找不到,我搜索其中一半。

1 个解决方案

#1


1  

The brute force method would be very similar to that of a 1D array, just with an extra loop, and a few more checks:

蛮力方法与1D数组非常相似,只需要一个额外的循环,还有一些检查:

public int[] findLocalMinimum(int[][] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr[i].length; j++) {

            int current = arr[i][j];

            if (i + 1 < arr.length    && current >= arr[i + 1][j] ||
                i - 1 >= 0            && current >= arr[i - 1][j] ||
                j + 1 < arr[i].length && current >= arr[i][j + 1] ||
                j - 1 >= 0            && current >= arr[i][j - 1]) {
                continue;
            } else {
                return new int[] { i, j };
            }

        }
    }
    return new int[] { -1, -1 };
}

#1


1  

The brute force method would be very similar to that of a 1D array, just with an extra loop, and a few more checks:

蛮力方法与1D数组非常相似,只需要一个额外的循环,还有一些检查:

public int[] findLocalMinimum(int[][] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr[i].length; j++) {

            int current = arr[i][j];

            if (i + 1 < arr.length    && current >= arr[i + 1][j] ||
                i - 1 >= 0            && current >= arr[i - 1][j] ||
                j + 1 < arr[i].length && current >= arr[i][j + 1] ||
                j - 1 >= 0            && current >= arr[i][j - 1]) {
                continue;
            } else {
                return new int[] { i, j };
            }

        }
    }
    return new int[] { -1, -1 };
}