LeetCode 每日一题

1. Search a 2D Matrix

Medium

2226167Add to ListShare

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

Example 1:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,50]], target = 3
Output: true

Example 2:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,50]], target = 13
Output: false

Example 3:

Input: matrix = [], target = 0
Output: false

Constraints:

• m == matrix.length
• n == matrix[i].length
• 0 <= m, n <= 100
• -104 <= matrix[i][j], target <= 104

主要代码

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int row = matrix.length;
        

        if (row == 0) {
            return false;
        }
        int col = matrix[0].length;
        int len = row * col + 5;

        int[] tmp = new int[len];

        int k = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                tmp[k++] = matrix[i][j];
            }
        }


        int l = 0, r = k - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (tmp[mid] == target) {
                return true;
            } else if (tmp[mid] > target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }

        if (tmp[l] == target) {
            return true;
        }
        return false;
    }
}