Search a 2D Matrix II

https://leetcode.com/problems/search-a-2d-matrix-ii/description/

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

• Integers in each row are sorted in ascending from left to right.

• Integers in each column are sorted in ascending from top to bottom.

Thoughts

Brute-force是遍历整个矩阵，O(mn). 稍微优化可以遍历每一行时用二分法，O(mlgn). 但没有利用到列也排好了序的性质。因此可以先对首列做二分，减少一半的可能性，虽然时间复杂度上没减少。

Code

class Solution {
    private int binSearch(int[] nums, int target) {
        int start = 0, end = nums.length - 1;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] < target) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }

        return start;
    }

    public boolean searchMatrix(int[][] matrix, int target) {
        for (int[] nums : matrix) {
            if (nums.length > 0 && (nums[nums.length - 1] < target || nums[0] > target)) {
                continue;
            }
            if (nums.length > 0 && nums[binSearch(nums, target)] == target) {
                return true;
            }
        }
        return false;
    }
}

Analysis

时间复杂度为O(nlgm)

Ver.2

双指针 分别代表当前行和列. 从第一行最后一个元素开始. 当当前元素小于target时, 意味着整行都比target小, row+1; 当当前元素大于时, 意味着当前列从当前行往后的都比target大, col--.

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

        int row = 0;
        int col = matrix[0].length - 1;
        while (row <= matrix.length - 1 && col >= 0) {
            if (matrix[row][col] == target) {
                return true;
            } else if (matrix[row][col] < target) {
                row++;
            } else if (matrix[row][col] > target) {
                col--;
            }
        }

        return false;
    }
}

.