时间戳

首页 > 解决方案 > 在多维数组中查找坐标

java - 在多维数组中查找坐标

问题描述

我有一个int[][]像这样的数组：

int[][] arr = { {3, 4, 3, 5, -9}, 
                {0, 4, 4, -8, 6}, 
                {1, 1, 3, -9, 6}, 
                {4, 3, -2, 5, 6}};

实际问题是在二维数组中找到一个矩形，矩形的每个角与二维数组中的角元素具有相同的值。例如，角是 3、-9、4 和 6。生成的矩形是 [0, 2]、[0, 4]、[1, 2]、[1, 4] 处的那个。

我的尝试是首先找出每行所有 [3, -9] 的位置，例如，第一行在 [{0,0},{0,4}] 和 [ {0,2},{0,4}]。

我可以执行标准的嵌套for循环来查找每个 3 和每个 9：

for (int i = 0; i < arr.length; i++) {
    for (int j = 0; j < arr[i].length; j++) {
    // if value is 3, store the co-ordinates
    // if value is 9, store the co-ordinates (separately)
    }
}

但后来我被迫遍历 2 个列表（3 和 -9 的）并检查每个 3 是否在同一行上有一个 -9，并且它在该行的后面，如果是这样，将两个坐标组合并存储在一起。

然后当然我必须对 4s 和 6s 做同样的事情，它很快就变得一团糟。

也许我在看这一切都是错误的，并且可以被认为是XY Problem。

我的问题：如何在二维数组中找到一个矩形，该矩形的角与二维数组的外角匹配？

标签： javamultidimensional-array

解决方案

普通搜索呢？

public static List<Point> findRectangle(int[][] arr) {
    int height = arr.length;
    int width = arr[0].length;

    for (int rowTop = 0; rowTop < height - 1; rowTop++) {
        for (int colLeft = rowTop == 0 ? 1 : 0; colLeft < width - 1; colLeft++) {
            // find new left-top corner
            if (arr[rowTop][colLeft] != arr[0][0])
                continue;

            int colRight = colLeft + 1;

            while (colRight < width && arr[rowTop][colRight] != arr[0][width - 1]) {
                colRight++;
            }

            if (colRight == width)
                continue;

            // find new left-bottom corner
            int rowBottom = rowTop + 1;

            while (rowBottom < height && arr[rowBottom][colLeft] != arr[height - 1][0]) {
                rowBottom++;
            }

            if (rowBottom == height || arr[rowBottom][colRight] != arr[height - 1][width - 1])
                continue;

            return Arrays.asList(
                    new Point(rowTop, colLeft),
                    new Point(rowTop, colRight),
                    new Point(rowBottom, colLeft),
                    new Point(rowBottom, colRight));
        }
    }

    return Collections.emptyList();
}

public static final class Point {

    private final int row;
    private final int col;

    public Point(int row, int col) {
        this.row = row;
        this.col = col;
    }
}

推荐阅读