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

What is the best and efficient way to get the maximum i, which is the number of rows and j, which is the number of columns, in two a dimensional array?

获得最大i的最佳和最有效的方法是什么，即两个一维数组中的行数和j，即列数？

Hopefully, the time complexity can lower than O(n) for every case. No loop here and can still find the maximum j.

希望时间复杂度可以低于每个案例的O（n）。这里没有循环，仍然可以找到最大的j。

For example, if I have an array like this one

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

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

Then I want to get i = 3 and j = 10 here as a result.

然后我希望得到i = 3和j = 10。

May anyone can help me?

愿任何人都可以帮助我吗？

5 个解决方案

#1

You can avoid writing the loop yourself, but you can't avoid having a runtime of at least O(n), since "someone" needs to loop the source array.

你可以避免自己编写循环，但是你不能避免运行时至少有O（n），因为“某人”需要循环源数组。

Here is a possible way to do that in Java 8:

这是在Java 8中执行此操作的可能方法：

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

This returns the maximum length of a "row" in your 2d array:

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

10

10

Another version which avoids using the Comparator and therefore might be a bit easier to read:

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

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

arr is supposed to be your source array.

arr应该是你的源数组。

Edit: the older version used .max(Integer::max), which is wrong and causes wrong results. See this answer for an explanation.

编辑：旧版本使用.max（Integer :: max），这是错误的并导致错误的结果。请参阅此答案以获得解释。

#2

Assuming your array does not contain null values, you could write something like this:

假设您的数组不包含空值，您可以编写如下内容：

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));
}

If you happen to create a parallel stream from the array instead, you could speed up this even further.

如果您碰巧从阵列中创建并行流，则可以进一步加快速度。

Another option is to sort the array by length, the quicksort usually has an average complexity of O(n*log(n)) therefore this isn't faster;

另一个选择是按长度对数组进行排序，快速排序的平均复杂度通常为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));

#3

Your i is the number of rows, which is simply the length of the 2-D array (assuming you are OK with including empty/null rows in this count).

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

The max row length j, however, would require iterating over all the rows to find the row i having the maximum arr[i].length.

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

#4

There will always be a loop¹, even though the looping will be implicit in solutions that use Java 8 streams.
总会有一个loop1，即使循环将隐含在使用Java 8流的解决方案中。
The complexity of getting the max number of columns is O(N) where N is the number of rows.
获得最大列数的复杂性是O（N），其中N是行数。
Implicit looping using streams probably will be less efficient than explicit looping using for.
使用流的隐式循环可能比使用for的显式循环效率低。

Here's a neat solution using a for loop

这是一个使用for循环的简洁解决方案

int max = o;
for (int i = 0; i < array.length; i++) {
    max = Math.max(max, array[i].length);
}

This works in the edge-case where array.length == 0, but if array or any array[i] is null you will get a NullPointerException. (You could modify the code to allow for that, but if the nulls are not expected, an NPE is probably a better outcome.)

这适用于array.length == 0的边缘情况，但如果数组或任何数组[i]为null，则会得到NullPointerException。（您可以修改代码以允许这样做，但如果不期望空值，NPE可能是更好的结果。）

^{1 - In theory, you could unroll the loops for all cases of array.length from 0 to Integer.MAX_VALUE, you would not need a loop. However, the code would not compile on any known Java compiler because it would exceed JVM limits on bytecode segments, etcetera. And the performance would be terrible for various reasons.}

1 - 理论上，你可以为所有array.length从0到Integer.MAX_VALUE的情况展开循环，你不需要循环。但是，代码不会在任何已知的Java编译器上编译，因为它会超过字节码段上的JVM限制等等。由于各种原因，表现会很糟糕。

#5

You could try this way: loop on the array and find the max length of the arrays which is in this array

您可以尝试这种方式：在数组上循环并找到此数组中数组的最大长度

byte[][] arrs = new byte[3][];
int maxLength = 0;
for (byte[] array : arrs) {
    if (maxLength < array.length) {
        maxLength = array.length;
    }
}

#1