Получить максимальную длину строки и столбца в двумерном массиве 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

Вы можете избежать написания Петля себя, но вы не можете избежать иметь время выполнения не менее O(n), так как «кому-то» необходимо закодировать исходный массив.

Вот возможный способ сделать это в Java 8:

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

Это возвращает максимальную длину "строки" в вашем 2d массива:

Другая версия, которая позволяет избежать использования Comparator и поэтому может быть немного легче читать:

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

---

arr должен быть ваш исходный массив.

Редактировать: в старой версии используется .max(Integer::max), что является неправильным и приводит к неправильным результатам. См. this answer для пояснения.

Answer 2

Ваше i - это количество строк, которое представляет собой просто length из 2-мерного массива (при условии, что вы в порядке, включая пустые/нулевые строки в этом счетчике).

Максимальная длина строки j, однако, потребует повторения по всем строкам, чтобы найти строку i, имеющую максимум arr[i].length.

Answer 3

Вы могли бы попробовать этот способ: цикл по массиву и найти максимальную длину массива, который находится в этом массиве

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

Answer 4

Если предположить, что массив не содержит нулевые значения, вы могли бы написать что-то вроде этого:

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

Если вы случайно создать параллельный поток из массива вместо этого, вы могли бы ускорить это еще дальше.

Другим вариантом является сортировка массива по длине, quicksort обычно имеет среднюю сложность 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 5

1. Там всегда будет петля , даже несмотря на то, перекручивание будет неявное в растворах, которые используют Java-8 потоков.
2. Сложность получения максимального количества столбцов O(N) где N - это количество строк.
3. Неявный цикл с использованием потоков, вероятно, будет менее эффективным, чем явный цикл, используя for.

Вот изящное решение с использованием for петли

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

Это работает в ребре-случае, когда array.length == 0, но если array или любой array[i] является null вы получите NullPointerException. (Вы можете изменить код, чтобы для этого, но если Нуль- не ожидается, NPE, вероятно, лучший результат.)

---

^{1 - В теории, можно раскатать петли для всех случаев array.length от 0 до Integer.MAX_VALUE, вам не нужен цикл. Однако код не будет компилироваться ни на одном известном компиляторе Java, поскольку он превысит лимиты JVM на сегментах байт-кода и т. Д. И производительность была бы ужасной по разным причинам.}