Search a 2D Matrix II

    This matrix has the following properties:

    • Integers in each column are sorted from up to bottom.
    • No duplicate integers in each row or column.

    Example

    Consider the following matrix:

    Challenge

    O(m+n) time and O(1) extra space

    1. 复杂度要求——O(m+n) time and O(1) extra space，同时输入只满足自顶向下和自左向右的升序，行与行之间不再有递增关系，与上题有较大区别。时间复杂度为线性要求，因此可从元素排列特点出发，从一端走向另一端无论如何都需要m+n步，因此可分析对角线元素。
    2. 首先分析如果从左上角开始搜索，由于元素升序为自左向右和自上而下，因此如果target大于当前搜索元素时还有两个方向需要搜索，不太合适。
    3. 如果从右上角开始搜索，由于左边的元素一定不大于当前元素，而下面的元素一定不小于当前元素，因此每次比较时均可排除一列或者一行元素（大于当前元素则排除当前行，小于当前元素则排除当前列，由矩阵特点可知），可达到题目要求的复杂度。

    在遇到之前没有遇到过的复杂题目时，可先使用简单的数据进行测试去帮助发现规律。

    Python

    Java

    1. 首先对输入做异常处理，不仅要考虑到matrix为空串，还要考虑到matrix[0]也为空串。
    2. 在找出后应继续向左搜索其他可能相等的元素，下方比当前元素大，故排除此列。

    复杂度分析

    由于每行每列遍历一次，故时间复杂度为 O(m + n).