获取java二维数组中行和列的最大长度

Question

在二维数组中获取最大i，即行数和j，即列数的最佳和有效方法是什么？

希望在每种情况下，时间复杂度都低于O（n）。这里没有循环，仍然可以找到最大j。

例如，如果我有一个这样的数组

[
    [18,18,19,19,20,22,22,24,25,26],
    [1,2,3],
    [0,0,0,0]
]

然后我想在这里得到i = 3和j = 10作为结果。

有人能帮我吗？

Answer 1

您的i是行数，它只是2-D数组的长度（假设您可以在此计数中包含空行/空行）。

然而，最大行长度j需要遍历所有行以找到具有最大arr[i].长度的行i。

Answer 2

假设您的数组不包含空值，您可以这样写:

private static final Comparator<int[]> lengthComparator = new Comparator<int[]> () {
    @Override
    public int compare(int[] o1, int[] o2) {
        return o1.length - o2.length;
    }
};

@Test
public void soArrayMaxLength() {

    int[][] array = new int[][] {
        {18,18,19,19,20, 22, 22, 24, 25,26},
        {1,2,3},
        {0,0,0,0}
    };

    int i = array.length;

    Optional<int[]> longestArray = 
            Arrays.stream(array)
            .max(lengthComparator);

    int j = longestArray.isPresent() ? longestArray.get().length : 0;

    System.out.println(String.format("i=%d j=%d", i, j));
}

如果您碰巧从数组创建了一个并行流，您可以进一步加快速度。

另一种选择是按长度对数组进行排序，快速排序通常具有O（n*log（n））的平均复杂度，因此这并不快;

    int i = array.length;
    Arrays.parallelSort(array, lengthComparator);

    int j = array[i-1].length;

    System.out.println(String.format("i=%d j=%d", i, j));

Answer 3

您可以避免自己编写循环，但您无法避免至少有一个＜code＞O（n）

在Java 8中有一种可能的方法:

Arrays.stream(arr).map(row -> row.length).max(Integer::compare).get();

这将返回2d数组中“行”的最大长度：

10

另一个版本避免使用比较器，因此可能更容易阅读：

Arrays.stream(arr).mapToInt(row -> row.length).max().getAsInt();

arr 应该是您的源数组。

编辑：旧版本使用＜code＞。max（Integer：：max），这是错误的，会导致错误的结果。有关解释，请参阅此答案。