Вернуть анти-диагонали


Дать П*П квадратной матрицы, возвратить массив из своей анти-диагонали. Рассмотрим пример более подробно.

Пример:

Вход:

1 2 3
4 5 6
7 8 9

Return the following :

[ 
  [1],
  [2, 4],
  [3, 5, 7],
  [6, 8],
  [9]
]

Это мой подход к данному вопросу:

public class Solution {
    public ArrayList<ArrayList<Integer>> diagonal(ArrayList<ArrayList<Integer>> A) {

        //The total number of internal rows in the final list will be 2*noofrows(A) - 1
        int size = 2*A.get(0).size() - 1;
        ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
        int count = 0;

        //Count of the number of rows
        int r = A.size();

        //Time complexity: O(size*r^2)
        //Space complexity: O(size)
        while( count < size)
            {
                ArrayList<Integer> temp = new ArrayList<>();
                for( int i = 0; i < r; i++ )
                {
                    for( int j = 0; j < r; j++ )
                        {
                            if( ((i + j) == count))
                                temp.add(A.get(i).get(j));

                            //Continue when the indices sum up to be > count
                            if((i + j) > count )
                                continue;
                        }
                }
                ans.add(temp);
                count++;
            }
        return ans;
    }

У меня есть следующие вопросы относительно моего кода:

1) Есть ли лучший подход, чтобы решить эту проблему?

2) Как я могу улучшить свое время и сложность пространства?

3) есть какие-то лишние шаги, которые могут быть удалены?

Ссылка



Комментарии
3 ответа

Я придумал решение, которое повышает сложность время:
Так вот в чем дело: решение на самом деле перестановка матрицы, значения(Р^2) должна быть возможность: побывать в каждой ячейке матрицы один раз, определение его нахождения в растворе.

и это понятно: найти руководителей анти-диагонали, и для каждого из них, найти все ее члены.
найти глав: итерации по первой строке, затем (когда вы достигли конца строки) перебрать последней колонке.
для каждой ячейки в вышеуказанных итерации, начать собирать анти-диагональных членов, продвигая на одну строку вниз, один столбец влево, пока один выходит за границы матрицы.

несколько заметок на выложили код:


  1. определяют переменные с типами интерфейсов: List<List<Integer>> ans = new ArrayList<>(); этот метод включает в себя Аргументы и возвращаемое значение. Это позволит вам изменить конкретную реализацию с минимальными изменениями.

  2. используйте короткую форму если (без скобок) рассудительно. это делает код менее понятным и склонен к ошибкам. Некоторые ппл будет сказать, не используйте это вообще. когда я использую его, я поставил условие и действие в той же строке:
    if( ((i + j) == count)) temp.add(A.get(i).get(j));

  3. Я думаю, что в этих видах вопросов, где входной сигнал известен и не меняется, массивы лучше всего подходит тогда коллекциях, поскольку они предлагают более лаконичный синтаксис: A[i][j] более понятно тогда A.get(i).get(j)

  4. соглашения об именовании переменных начинать с нижнего регистра.

1
ответ дан 17 февраля 2018 в 09:02 Источник Поделиться

почему бы вам не попробовать, чтобы сохранить ваш алгоритм как можно проще?


  • одна вещь, чтобы держать вещи простыми в использовании int[][] в качестве источника

  • вы можете прямо вычислить длину каждой диагонали

  • вы можете напрямую рассчитать показатель (х/г) от каждого элемента диагонали

  • вы можете рассчитать по диагонали сверху и справа в один шаг

  • если вы инит ваш результат вы можете просто установить diagonales на его индекс

что приводит к ответы на ваш вопрос:


  1. Есть ли лучший подход, чтобы решить эту проблему?
    => это более чистыми, если вы не используете Listкогда это не требуется, лучше использовать примитивы

  2. Как я могу улучшить свое время и сложность пространства?
    => вы можете пропустить итерацию по матрице если подсчитать признак напрямую

  3. Есть какие-то лишние шаги, которые могут быть удалены?
    => нет код является избыточным, то алгоритм (см. выше) избыточна и уже исправлена


int [][] src = ...
int n = src.length; //it's n because it's an N x N-Matrix
List<Integer[]> result = new ArrayList<>(n);
for (int i = 0; i < 2*n-1; i ++){
result.add(new Integer[]{}); //initialize the result
}
for (int c = 0; c < n; c ++){ //c = column
Integer [] diagonalTop = new Integer[c+1];
Integer [] diagonalRight = new Integer[c+1];
for(int s = 0; s <= c; s++){//s = step in diagonal
int xTop = c-s;
int yTop = c-xTop;
int xRight = n-s-1;
int yRight = n - c + s -1;
diagonalTop[c-s] = Integer.valueOf(src[xTop][yTop]);
diagonalRight[s] = Integer.valueOf(src[yRight][xRight]);
}
result.set(c,diagonalTop ); //adding (setting) at the proper index
if(c < n-1){
result.set(2*n-c-2, diagonalRight ); //adding (setting) at the proper index
}
}

1
ответ дан 19 февраля 2018 в 12:02 Источник Поделиться


        //The total number of internal rows in the final list will be 2*noofrows(A) - 1
int size = 2*A.get(0).size() - 1;
...

//Count of the number of rows
int r = A.size();


Количество строк A.get(0).size() или A.size()? Да, они одинаковые (потому что спец говорит, что матрица квадратная), но комменты активно сбивает с толку, и это важно, потому что направление antidiagonals зависит от того, первый индекс в строке или столбце.


Что ваш отступ конвенции? Что бы это ни было, этот код не похоже, чтобы постоянно следовать ему. Иногда скобки смещены относительно их контроля while / forи иногда они не являются.



                    for( int j = 0; j < r; j++ )
{
if( ((i + j) == count))
temp.add(A.get(i).get(j));

//Continue when the indices sum up to be > count
if((i + j) > count )
continue;
}


Две вещи:

Во-первых, continue; заявление в конце цикла точно ничего. Этот код напрямую эквивалент

                    for( int j = 0; j < r; j++ )
{
if( ((i + j) == count))
temp.add(A.get(i).get(j));
}

Я думаю, что вы хотели, либо break; или им и дальше, но последние должны использоваться очень редко, потому что это не часто ясный способ структурировать код.

Во-вторых, как бы вы оптимизировать следующий код?

for (int k = 0; k < 100; k++)
{
if (k == 17) System.out.println(myArray[k]);
}

Спойлер:


System.out.println(myArray[17]);

Тот же принцип применим к петле над j.

1
ответ дан 19 февраля 2018 в 03:02 Источник Поделиться