Diaqonal Traverse LeetCode Həlli

Problem bəyanat

Diaqonal Traverse LeetCode Həlli – Verilmişdir m x n matris mat, qayıt diaqonal qaydada massivin bütün elementlərinin massivi.

Pin

Input: mat = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,4,7,5,3,6,8,9]

Izahat

NxM matrisinin diaqonallarının indekslərini nəzərdən keçirək. Nümunə olaraq 4×4 matrisi istifadə edək:

(0, 0) (0, 1) (0, 2) (0, 3)


(1, 0) (1, 1) (1, 2) (1, 3)


(2, 0) (2, 1) (2, 2) (2, 3)


(3, 0) (3, 1) (3, 2) (3, 3)


Birinci diaqonaldır (0, 0). İkincisi (0, 1), (1, 0), üçüncüsüdür (2, 0), (1, 1), (0, 2)Və sairə

Bu sıra cəmi aydın olmalıdır i və sütun j diaqonalın indeksinə bərabərdir (diaqonal ədəd – 1). məsələn, ikinci diaqonal üçün (indeks 1), bütün mümkün cütləşmələr (i, j) cəmi 1, yəni i + j = 1 2-ci diaqonal üçün. Maksimum diaqonal indeks sadədir ((N-1) + (M-1)) = N + M - 2

Beləliklə, problemi həll etmək üçün sadəcə olaraq bütün mümkün diaqonal indeksləri təkrarlamalıyıq (bunu kimi qeyd edin s) və bütün mümkün cütləri (i, j) tapın i + j = s. Özümüzü narahat etməli olduğumuz yeganə şey nizamdır. Diaqonal indeksin cüt və ya tək olmasına baxaraq sıralamağı tapa bilərik. Diaqonal indeks bərabər olduqda, birinci cütün olmasını istəyirik (s, 0) və ilk cütün olmasını istəyəndə qəribə olduqda (0, s), və biz i/j-ni müvafiq olaraq 1 azaldırıq və ya artırırıq.

Kodu

Diaqonal keçid üçün C++ kodu

class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
        if(matrix.empty()) return {};
        
        const int N = matrix.size();
        const int M = matrix[0].size();
        
        vector<int> res;
        for(int s = 0; s <= N + M - 2; ++s)
        {
            // for all i + j = s
            for(int x = 0; x <= s; ++x) 
            {
                int i = x;
                int j = s - i;
                if(s % 2 == 0) swap(i, j);

                if(i >= N || j >= M) continue;
                
                res.push_back(matrix[i][j]);
            }
        }
        
        return res;
    }
};

Diaqonal keçid üçün Java kodu

class Solution {
    public int[] findDiagonalOrder(int[][] mat) {
        HashMap<Integer,List<Integer>> map=new HashMap<>();
        for (int i=0;i<mat.length;i++) {
            for(int j=0;j<mat[i].length;j++) {
                int key=i+j;
                if(map.containsKey(key)) map.get(key).add(mat[i][j]);
                else {
                    map.put(key,new ArrayList<Integer>());
                    map.get(key).add(mat[i][j]);
                     }
            }
        }
        int curr=0;
        int index=0;
        boolean check=false;
        int[] ans=new int[mat.length*mat[0].length];
        while (true) {
            if(!map.containsKey(curr)) break;
            List<Integer> a=map.get(curr);
            if(check) {
                for(int i=0;i<a.size();i++) {
                    ans[index++]=a.get(i);
                }
                check=!check;
            }
            else {
                for(int i=a.size()-1;i>=0;i--) {
                    ans[index++]=a.get(i);
                }
                check=!check;
            }
            curr++;
        }
        return ans;
    }
}

Diaqonal keçid üçün Python kodu

class Solution(object):
    def findDiagonalOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        result = [ ]
        dd = collections.defaultdict(list)
        if not matrix: return result
        # Step 1: Numbers are grouped by the diagonals.
        # Numbers in same diagonal have same value of row+col
        for i in range(0, len(matrix)):
            for j in range(0, len(matrix[0])):
                dd[i+j+1].append(matrix[i][j]) # starting indices from 1, hence i+j+1.
        # Step 2: Place diagonals in the result list.
        # But remember to reverse numbers in odd diagonals.
        for k in sorted(dd.keys()):
            if k%2==1: dd[k].reverse()
            result += dd[k]
        return result

Diaqonal Traverse LeetCode Həlli üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi

O (n ^ 2)

Kosmik Mürəkkəblik

O (n ^ 2)