一：除自身以外数组的乘积

image-20251005223501793

1. 左右乘积列表

用两个数组分别记录左右两端的乘积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int length = nums.size();
        vector<int> left(length);
        vector<int> right(length);
        vector<int> result(length);
        left[0] = 1;
        right[length -  1] = 1;
        for (int i = 1, j = length - 2; i <length && j >= 0; ++i, --j)
        {
            left[i] = nums[i - 1] * left[i - 1];
            right[j] = nums[j + 1] * right[j + 1];
        }
        for (int i = 0; i < length; ++i)
            result[i] = left[i] * right[i];
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int length = nums.length;
        int[] left = new int[length] ;
        int[] right = new int[length] ;
        int[] result = new int[length] ;
        left[0] = 1;
        right[length -  1] = 1;
        for (int i = 1, j = length - 2; i <length && j >= 0; ++i, --j)
        {
            left[i] = nums[i - 1] * left[i - 1];
            right[j] = nums[j + 1] * right[j + 1];
        }
        for (int i = 0; i < length; ++i)
            result[i] = left[i] * right[i];
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        length = len(nums)
        left = [0] * length
        right = [0] * length
        result = [0] * length
        left[0] = 1
        right[length -  1] = 1
        for i in range(1, length):
            left[i] = nums[i - 1] * left[i - 1]
        for j in reversed(range(length - 1)):
            right[j] = nums[j + 1] * right[j + 1]
        for i in range(length):
            result[i] = left[i] * right[i]
        return result

image-20251005223704993

2. 空间复杂度O(1)O(1)的方法

用结果数组先作为左乘积列表，然后使用临时变量记录每个右乘积并更新数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int length = nums.size();
        vector<int> result(length);
        result[0] = 1;
        for (int i = 1; i <length; ++i)
            result[i] = nums[i - 1] * result[i - 1];
        int rightMul = 1;
        for (int j = length - 1; j >= 0; --j)
        {
            result[j] = result[j] * rightMul;
            rightMul *= nums[j];
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int length = nums.length;
        int[] result = new int[length] ;
        result[0] = 1;
        for (int i = 1; i <length; ++i)
            result[i] = nums[i - 1] * result[i - 1];
        int rightMul = 1;
        for (int j = length - 1; j >= 0; --j)
        {
            result[j] = result[j] * rightMul;
            rightMul *= nums[j];
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        length = len(nums)
        result = [0] * length
        result[0] = 1
        for i in range(1, length):
            result[i] = nums[i - 1] * result[i - 1]
        rightMul = 1
        for j in reversed(range(length)):
            result[j] = result[j] * rightMul
            rightMul *= nums[j]
        return result

image-20251005223720269

二：矩阵置零

image-20251005233019423

1. 使用标记数组

通过两个数组来记录二维数组中某行或这某列是否包含零

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int nRow = matrix.size();
        int nCol = matrix[0].size();
        vector<int> vRow(nRow);
        vector<int> vCol(nCol);
        for (int i = 0; i < nRow; ++i)
            for (int j = 0; j < nCol; ++j)
                if (matrix[i][j] == 0) vRow[i] = vCol[j] = 1;
        for (int i = 0; i < nRow; ++i)
            for (int j = 0; j < nCol; ++j)
                if (vRow[i] == 1 || vCol[j] == 1) matrix[i][j] = 0;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public void setZeroes(int[][] matrix) {
        int nRow = matrix.length;
        int nCol = matrix[0].length;
        int[] vRow = new int[nRow];
        int[] vCol = new int[nCol];
        for (int i = 0; i < nRow; ++i)
            for (int j = 0; j < nCol; ++j)
                if (matrix[i][j] == 0) vRow[i] = vCol[j] = 1;
        for (int i = 0; i < nRow; ++i)
            for (int j = 0; j < nCol; ++j)
                if (vRow[i] == 1 || vCol[j] == 1) matrix[i][j] = 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        nRow = len(matrix)
        nCol = len(matrix[0])
        vRow = [0] * nRow
        vCol = [0] * nCol
        for i in range(nRow):
            for j in range(nCol):
                if (matrix[i][j] == 0): vRow[i] = vCol[j] = 1
        for i in range(nRow):
            for j in range(nCol):
                if (vRow[i] == 1 or vCol[j] == 1): matrix[i][j] = 0

image-20251005233052575

2. 使用两个标记变量

使用第一行和第一列来记录其余位置的零，再使用两个标记变量来记录第一行和第一列的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int nRow = matrix.size();
        int nCol = matrix[0].size();
        bool firstRow = false;
        bool firstCol = false;
        for (int i = 0; i < nRow; ++i)
            if (matrix[i][0] == 0) firstCol = true;
        for (int i = 0; i < nCol; ++i)
            if (matrix[0][i] == 0) firstRow = true;

        for (int i = 1; i < nRow; ++i)
            for (int j = 1; j < nCol; ++j)
                if (matrix[i][j] == 0) matrix[i][0] = matrix[0][j] = 0;
        for (int i = 1; i < nRow; ++i)
            for (int j = 1; j < nCol; ++j)
                if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;
        if (firstCol == true)
            for (int i = 0; i < nRow; ++i)
                matrix[i][0] = 0;
        if (firstRow == true)
            for (int i = 0; i < nCol; ++i)
                matrix[0][i] = 0;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public void setZeroes(int[][] matrix) {
        int nRow = matrix.length;
        int nCol = matrix[0].length;
        boolean firstRow = false;
        boolean firstCol = false;
        for (int i = 0; i < nRow; ++i)
            if (matrix[i][0] == 0) firstCol = true;
        for (int i = 0; i < nCol; ++i)
            if (matrix[0][i] == 0) firstRow = true;

        for (int i = 1; i < nRow; ++i)
            for (int j = 1; j < nCol; ++j)
                if (matrix[i][j] == 0) matrix[i][0] = matrix[0][j] = 0;
        for (int i = 1; i < nRow; ++i)
            for (int j = 1; j < nCol; ++j)
                if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;
        if (firstCol == true)
            for (int i = 0; i < nRow; ++i)
                matrix[i][0] = 0;
        if (firstRow == true)
            for (int i = 0; i < nCol; ++i)
                matrix[0][i] = 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        nRow = len(matrix)
        nCol = len(matrix[0])
        firstRow = False
        firstCol = False
        for i in range(nRow):
            if (matrix[i][0] == 0): firstCol = True
        for i in range(nCol):
            if (matrix[0][i] == 0): firstRow = True

        for i in range(1, nRow):
            for j in range(1, nCol):
                if (matrix[i][j] == 0): matrix[i][0] = matrix[0][j] = 0
        for i in range(1, nRow):
            for j in range(1, nCol):
                if (matrix[i][0] == 0 or matrix[0][j] == 0): matrix[i][j] = 0
        if (firstCol == True):
            for i in range(nRow):
                matrix[i][0] = 0
        if (firstRow == True):
            for i in range(nCol):
                matrix[0][i] = 0

image-20251005233118603

3. 使用一个标记变量

用左上角的元素作为标记变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int nRow = matrix.size();
        int nCol = matrix[0].size();
        bool firstFlag = false;
        for (int i = 0; i < nRow; ++i)
        {
            if (matrix[i][0] == 0) firstFlag = true;
            for (int j = 1; j < nCol; ++j)
                if (matrix[i][j] == 0) matrix[i][0] = matrix[0][j] = 0;
        }
        for (int i = nRow - 1; i >= 0; --i)
        {
            for (int j = 1; j < nCol; ++j)
                if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;
            if (firstFlag == true)
                matrix[i][0] = 0;
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public void setZeroes(int[][] matrix) {
        int nRow = matrix.length;
        int nCol = matrix[0].length;
        boolean firstFlag = false;
        for (int i = 0; i < nRow; ++i)
        {
            if (matrix[i][0] == 0) firstFlag = true;
            for (int j = 1; j < nCol; ++j)
                if (matrix[i][j] == 0) matrix[i][0] = matrix[0][j] = 0;
        }
        for (int i = nRow - 1; i >= 0; --i)
        {
            for (int j = 1; j < nCol; ++j)
                if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;
            if (firstFlag == true)
                matrix[i][0] = 0;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        nRow = len(matrix)
        nCol = len(matrix[0])
        flag = False
        for i in range(nRow):
            if (matrix[i][0] == 0): flag = True
            for j in range(1, nCol):
                if (matrix[i][j] == 0): matrix[i][0] = matrix[0][j] = 0
        for i in reversed(range(nRow)):
            for j in range(1, nCol):
                if (matrix[i][0] == 0 or matrix[0][j] == 0): matrix[i][j] = 0
            if flag == True:
                matrix[i][0] = 0

image-20251005233143358

三：螺旋矩阵

image-20251006125553376

1. 模拟

定义一个旋转方向，当遇到边界和访问过的节点进行旋转（属于暴力）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int rowCnt = matrix.size();
        int colCnt = matrix[0].size();
        enum Rule {leftToright, upTodow, rightToleft, downToup};
        Rule myRule = Rule::leftToright;
        vector<int> results;
        vector<vector<int>> visited(rowCnt, vector<int>(colCnt));
        int row = 0, col = 0;
        for (int i = 0; i < rowCnt * colCnt; ++i)
        {
            int nextRow = row, nextCol = col;
            results.emplace_back(matrix[row][col]);
            visited[row][col] = 1;
            if (myRule == 0) nextCol = col + 1;
            if (myRule == 1) nextRow = row + 1;
            if (myRule == 2) nextCol = col - 1;
            if (myRule == 3) nextRow = row - 1;
            if (nextRow >= rowCnt || nextRow < 0 || nextCol >= colCnt || nextCol < 0 || visited[nextRow][nextCol] == 1)
                myRule = static_cast<Rule>((myRule + 1) % 4);
            if (myRule == 0) ++col;
            if (myRule == 1) ++row;
            if (myRule == 2) --col;
            if (myRule == 3) --row;
        }
        return results;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        int rowCnt = matrix.length;
        int colCnt = matrix[0].length;
        List<Integer> results = new ArrayList<>();
        int[][] visited = new int[rowCnt][colCnt];
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int directionIndex = 0;
        int row = 0, col = 0;
        for (int i = 0; i < rowCnt * colCnt; ++i)
        {
            results.add(matrix[row][col]);
            visited[row][col] = 1;
            int nextRow = row + directions[directionIndex][0];
            int nextCol = col + directions[directionIndex][1];
            if (nextRow >= rowCnt || nextRow < 0 || nextCol >= colCnt || nextCol < 0 || visited[nextRow][nextCol] == 1)
                directionIndex = (directionIndex + 1) % 4;
            row += directions[directionIndex][0];
            col += directions[directionIndex][1];
        }
        return results;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        rowCnt, colCnt = len(matrix), len(matrix[0])
        results = []
        visited = [[0] * colCnt for _ in range(rowCnt)]
        directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
        direction_index = 0  
        row, col = 0, 0
        for _ in range(rowCnt * colCnt):
            results.append(matrix[row][col])
            visited[row][col] = True
            next_row = row + directions[direction_index][0]
            next_col = col + directions[direction_index][1]
            if not (0 <= next_row < rowCnt and 0 <= next_col < colCnt and not visited[next_row][next_col]):
                direction_index = (direction_index + 1) % 4
            row += directions[direction_index][0]
            col += directions[direction_index][1]
        return results

image-20251006125710190

2. 按层模拟

每一圈相当于将最外围的数据输出，需要四个循环将四个边界输出，然后通过大的循环来遍历每一圈，注意圈的截止条件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if (matrix.size() == 0 || matrix[0].size() == 0) return {};
        int bottom = matrix.size() - 1;
        int right = matrix[0].size() - 1;
        vector<int> results;
        int left = 0, top = 0;
        while (left <= right && top <= bottom)
        {
            for (int i = left; i <= right; ++i) results.emplace_back(matrix[top][i]);
            for (int i = top + 1; i <= bottom; ++i) results.emplace_back(matrix[i][right]);
            if (left < right && top < bottom) 			// 到这里可能剩余不足围成圈，如1*n或n*1，此时前两个循环已经足够处理，如果不加以限制，那么在n大于1的情况下，下述的循环将会有一个进入导致最后结尾出现多余的数据
            {
                for (int i = right - 1; i > left; --i) results.emplace_back(matrix[bottom][i]);
                for (int i = bottom; i > top; --i) results.emplace_back(matrix[i][left]);
            }
            ++left;
            ++top;
            --bottom;
            --right;
        }
        return results;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        int bottom = matrix.length - 1;
        int right = matrix[0].length - 1;
        List<Integer> results = new ArrayList<>();
        int left = 0, top = 0;
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return results;
        while (left <= right && top <= bottom)
        {
            for (int i = left; i <= right; ++i) results.add(matrix[top][i]);
            for (int i = top + 1; i <= bottom; ++i) results.add(matrix[i][right]);
            if (left < right && top < bottom) 
            {
                for (int i = right - 1; i > left; --i) results.add(matrix[bottom][i]);
                for (int i = bottom; i > top; --i) results.add(matrix[i][left]);
            }
            ++left;
            ++top;
            --bottom;
            --right;
        }
        return results;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        bottom, right = len(matrix) - 1, len(matrix[0]) - 1
        results = list() 
        left, top = 0, 0
        while left <= right and top <= bottom:
            for i in range(left, right + 1): results.append(matrix[top][i])
            for i in range(top + 1, bottom + 1): results.append(matrix[i][right])
            if left < right and top < bottom:
                for i in range(right - 1, left, -1): results.append(matrix[bottom][i])
                for i in range(bottom, top, -1): results.append(matrix[i][left])
            left, right, top, bottom = left + 1, right - 1, top + 1, bottom - 1
        return results

image-20251006125700627

四：旋转图像

image-20251006164452720

1. 辅助数组

将旋转后的元素放入新的数组

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        auto result = matrix;
        int m = matrix.size();
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < m; ++j)
                result[j][m - 1 - i] = matrix[i][j];
        matrix.assign(result.begin(), result.end());
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public void rotate(int[][] matrix) {
        int m = matrix.length;
        int[][] result = new int[m][m];
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < m; ++j)
                result[j][m - 1 - i] = matrix[i][j];
        for (int i = 0; i < m; i++) {
            System.arraycopy(result[i], 0, matrix[i], 0, m);
        }
    }
}
1
2
3
4
5
6
7
8
class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)
        result = [[0] * n for _ in range(n)]
        for i in range(n):
            for j in range(n):
                result[j][n - 1 - i] = matrix[i][j]
        matrix[:] = result

image-20251006164652408

2. 原地旋转

参考移动数组的解决方案，这里旋转四次会回到原地，一圈会移动四个数据，那么也就是只需要旋转约四分之一的元素，n的奇的情况下，中间不需要管

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int m = matrix.size();
        for (int i = 0; i < m / 2; ++i)
            for (int j = 0; j < (m + 1) / 2; ++j)
            {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[m - 1 - j][i];
                matrix[m - j - 1][i] = matrix[m - i - 1][m - j - 1];
                matrix[m - i - 1][m - j - 1] = matrix[j][m - i - 1];
                matrix[j][m - 1 - i] = temp;
            }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public void rotate(int[][] matrix) {
        int m = matrix.length;
        for (int i = 0; i < m / 2; ++i)
            for (int j = 0; j < (m + 1) / 2; ++j)
            {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[m - 1 - j][i];
                matrix[m - j - 1][i] = matrix[m - i - 1][m - j - 1];
                matrix[m - i - 1][m - j - 1] = matrix[j][m - i - 1];
                matrix[j][m - 1 - i] = temp;
            }
    }
}
1
2
3
4
5
6
7
8
9
10
class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        m = len(matrix)
        for i in range(m // 2):
            for j in range((m + 1) // 2):
                temp = matrix[i][j]
                matrix[i][j] = matrix[m - 1 - j][i]
                matrix[m - j - 1][i] = matrix[m - i - 1][m - j - 1]
                matrix[m - i - 1][m - j - 1] = matrix[j][m - i - 1]
                matrix[j][m - 1 - i] = temp

image-20251006164708520

3. 翻转

先水平后主对角线，也可以先竖直

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int m = matrix.size();
        for (int i = 0; i < m / 2; ++i)
            for (int j = 0; j < m; ++j)
                swap(matrix[i][j], matrix[m - i - 1][j]);
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < i; ++j)
                swap(matrix[i][j], matrix[j][i]);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public void rotate(int[][] matrix) {
        int m = matrix.length;
        for (int i = 0; i < m / 2; ++i)
            for (int j = 0; j < m; ++j)
            {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[m - i - 1][j];
                matrix[m - i - 1][j] = temp;
            }
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < i; ++j)
            {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
    }
}
1
2
3
4
5
6
7
8
9
class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        m = len(matrix)
        for i in range(m // 2):
            for j in range(m):
                matrix[i][j], matrix[m - i - 1][j] = matrix[m - i - 1][j], matrix[i][j]
        for i in range(m):
            for j in range(i):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

image-20251006164721836

五：搜索二维矩阵

image-20251006173633479

1. 暴力

不写

image-20251006173907919

2. 二分

由于数组左右有序，对每一行使用二分从中间查找

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        for (auto& row : matrix)
        {
            auto it = lower_bound(row.begin(), row.end(), target);			// 返回不小于目标值的第一个元素的迭代器
            if (it != row.end() && *it == target) return true;
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        for (int[] row : matrix)
        {
            int index = searchInsert(row, target);
            if (index != -1) return true;
        }
        return false;
    }
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1, cur = right + 1;
        while (left <= right)
        {
            int mid = ((right - left) >> 1) + left;       // 防止int越界
            if (target == nums[mid]) return mid;
            else if (target < nums[mid])     
                right = mid - 1;
            else
                left = mid + 1;
        }
        return -1;
    }
}
1
2
3
4
5
6
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        for row in matrix:
            it = bisect.bisect_left(row, target)			
            if it < len(row) and row[it] == target: return True
        return False

image-20251006173827241

3. Z 字形查找

充分运用题目要求，第二种方法只有了一个条件，但数据从上往下也是递增，从右上角开始，横竖作为边界，也就是说如果某个位置的值小于目标值，行数可以加一，如果大于目标值，则列数应该减一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();
        int 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 if(matrix[i][j] < target) ++i;
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int 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 if(matrix[i][j] < target) ++i;
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m = len(matrix)
        n = len(matrix[0])
        i = 0
        j = n - 1
        while i < m and j >= 0:
            if (matrix[i][j] == target): return True
            elif (matrix[i][j] > target): j -= 1
            elif(matrix[i][j] < target): i += 1
        return False

image-20251006173812935