240. Search a 2D Matrix II

解法一

思路

I found that if we start from the left bottom cornor of the matrix, the right neighbor is always larger than the element, and the top neighbor is always less than the element. So we can set two pointers one move in column and the other move in row to find the target.
Basic idea is, while both pointers are not out of bound, we compare the target with the pivot element. If target is larger we move one step to the right, if smaller, we move one step to the top. If target is equal to the element, we return true.

代码

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int rows = matrix.length;
        if (rows == 0 || martix == null) {
            return false;
        }
        int cols = matrix[0].length;
        if (matrix[0].length == 0 || matrix == null) {
            return false;
        }

        int i = rows - 1;
        int j = 0;
        while (i >= 0 && j < cols) {
            if (target > matrix[i][j]) {
                j++;
            } else if (target < matrix[i][j]) {
                i--;
            } else {
                return true;
            }
        }
        return false;
    }
}

复杂度分析

• 时间复杂度
  The worst case would be when we start at the left bottom cornor and end at right top cornor. O(m + n).
• 空间复杂度
  O(1)

解法二

思路

代码

复杂度分析

时间复杂度

• 最好情况
• 最坏情况
• 平均情况
  空间复杂度

Takeaway

本作品采用《CC 协议》，转载必须注明作者和本文链接