java - 确定两个元素是否位于二维数组的同一行或同一列中的最快方法是什么？

Question

作为我的一个程序的一部分，我正在尝试检查二维数组中的两个元素是否属于同一行或同一列。我知道可能有很多方法可以解决这个问题，主要是循环和遍历数组，但我只是想知道：有没有快速的方法来确定这一点？

假设我有一个看起来像{{1, 2}, {3, 4}, {5, 6}}. 是否有任何快速的方法来确定它1并2属于同一行？几乎可以在 if 语句中将其评估为“如果 item 与 itemx属于同一行y，则这样做等等”？如果没有，那么最快的方法是什么？

标签： javaarraysloopsmultidimensional-arraydata-structures

Answer 1

使用行比使用列更容易解决此任务。你可以使用binarySearch方法。

此解决方案还适用于参差不齐的二维数组和无限数量的元素进行搜索。

public static void main(String[] args) {
    int[][] arr = {{1, 2, 3}, {4, 5}, {6, 7, 8}};
    System.out.println(sameRow(arr, 4, 5)); // true
    System.out.println(sameCol(arr, 3, 8)); // true
}

/**
 * @param arr      2d array.
 * @param elements 1d array of elements to search for.
 * @return whether any column of a 2d array contains all elements from a 1d array.
 */
public static boolean sameCol(int[][] arr, int... elements) {
    return IntStream
            // iterate through the columns
            .iterate(0, i -> i + 1)
            // take an array of values from the column, if any
            .mapToObj(i -> Arrays
                    // iterate through the rows
                    .stream(arr)
                    // take those rows where this column is present
                    .filter(row -> row.length > i)
                    // take the value from the column
                    .mapToInt(row -> row[i])
                    // int[] - column
                    .toArray())
            // until the columns are still present
            .takeWhile(col -> col.length > 0)
            // whether any column contains all the search elements
            .anyMatch(col -> containsAll(col, elements));
}

/**
 * @param arr      2d array.
 * @param elements 1d array of elements to search for.
 * @return whether any row of a 2d array contains all elements from a 1d array.
 */
public static boolean sameRow(int[][] arr, int... elements) {
    return Arrays.stream(arr).anyMatch(row -> containsAll(row, elements));
}

/**
 * @param a first array.
 * @param b second array.
 * @return whether the first array contains all elements from the second array.
 */
public static boolean containsAll(int[] a, int[] b) {
    return Arrays.stream(b).allMatch(i -> Arrays.binarySearch(a, i) > -1);
}

---

^{另请参阅：
•首先按列填充锯齿状二维数组
•检查一个数组是否是另一个数组的子集 - 特殊情况}