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 协议》,转载必须注明作者和本文链接
《L05 电商实战》
从零开发一个电商项目,功能包括电商后台、商品 & SKU 管理、购物车、订单管理、支付宝支付、微信支付、订单退款流程、优惠券等
《L03 构架 API 服务器》
你将学到如 RESTFul 设计风格、PostMan 的使用、OAuth 流程,JWT 概念及使用 和 API 开发相关的进阶知识。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!