[LC 240]. Search a 2D Matrix II

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 in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.

从top right corner开始,如果 target 就向左移一列。

从2D的角度,也是一种binary search

好好想算法就能很简单的一道题

有趣的是,[LC 74]. Search a 2D Matrix也可以用一摸一样的code解决,虽然这道题有多种不同的解法,例如treat 2D array as 1D.

以下是这段通用的code

    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
        int rows = matrix.length;
        int cols = matrix[0].length;
        int i = 0, j = cols - 1;
        while (i < rows && j >= 0) {
             if (matrix[i][j] == target) return true;
             else if (matrix[i][j] < target) {
                 i++;
             } else {
                 j--;
             }
        }
        
        return false;
    }

对74,另外一种1D的做法(要点:a[i] -> A[i/cols][i%cols])

    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
        int m = matrix.length;
        int n = matrix[0].length;
        int i = 0, j = m * n - 1;
        while (i <= j) {
            int mid = i + (j - i) / 2;
            if (matrix[mid / n][mid % n] < target) {
                i = mid + 1;
            } else if (matrix[mid / n][mid % n] > target) {
                j = mid - 1;
            } else {
                return true;
            }
        }
        return false;
 
    }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s