2D Matrix II Leetcode Həllini axtarın

Problem bəyanat

The 2D Matrix II LeetCode Həllini axtarın – “Search a 2D Matrix II” sizdən dəyər axtaran səmərəli alqoritm tapmağı xahiş edir target bir m x n tam matris matrix. Hər bir sətirdə, eləcə də sütundakı tam ədədlər artan sıra ilə çeşidlənir.

Misal:

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5

Output: true

Explanation:

• Biz asanlıqla müşahidə edə bilərik ki, matrisin hədəf dəyəri var, ona görə də cavabımız doğrudur.

Input:  matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20

Output: false

Explanation:

• Matrisdə hədəf dəyəri yoxdur, ona görə də yalan qaytarılır.

Yanaşma

Idea:

1. Bu problemi həll etmək üçün əsas fikir ondan faydalanmaqdır sıralanmış sıralar və sıralanmış sütunlar.
2. -dən başlayın xana (0,n-1).
3. Hüceyrə dəyərini hədəflə müqayisə edin:
   1. Onlar varsa bərabər, doğru qayıt.
   2. Hüceyrə dəyəri olarsa hədəfdən ciddi şəkildə artıqdır, bu o deməkdir ki, hədəf heç vaxt cari sütunda yatmayacaq, çünki cari sütundakı cari sıra indeksindən daha yüksək indeks cərgəsində olan bütün dəyərlər cari xanadan ciddi şəkildə daha çox dəyərə malik olacaq. Beləliklə, hədəfi axtarmaq üçün cari sütun indeksini azaldırıq.
   3. Hüceyrə dəyəri olarsa hədəfdən ciddi şəkildə azdır, bu o deməkdir ki, hədəf heç vaxt cari cərgədə yatmayacaq, çünki cari sütun indeksindən aşağı indeksdə olan cari sıradakı bütün dəyərlər cari xanadan ciddi şəkildə daha az dəyərə malik olacaq. Beləliklə, hədəfi axtarmaq üçün cari sıra indeksini artırırıq.

Pin

Matrisin çeşidlənməsi onu göstərir ki, alqoritmimizi sürətləndirmək üçün ikili axtarışdan istifadə etməyin bir yolu olmalıdır. Siz həmçinin Binary Search tətbiq edə bilərsiniz.

2D Matrix II Leetcode Həllinin Axtarış Kodu:

C++ Həlli:

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(),n = matrix[0].size(),i = 0,j = n - 1;
        while(i<m && j>=0){
            if(matrix[i][j]==target){
                return true;
            }
            else if(matrix[i][j]>target){
                j--;
            }
            else{
                i++;
            }
        }
        return false;
    }
};

Java Həlli:

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length,n = matrix[0].length,i = 0,j = n - 1;
        while(i<m && j>=0){
            if(matrix[i][j]==target){
                return true;
            }
            else if(matrix[i][j]>target){
                j--;
            }
            else{
                i++;
            }
        }
        return false;
    }
}

2D Matrix II Leetcode Həlli Axtarış üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi O(M+N) ümumi ildən maksimum sayı iterasiyaların sayı m + n-ə keçir.

Kosmik Mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O (1) çünki biz daimi boşluqdan istifadə edirik.

Referans: https://en.wikipedia.org/wiki/Binary_search_algorithm