LintCode 28. Search a 2D Matrix 原创Java参考解答

LintCode 28. Search a 2D Matrix 原创Java参考解答

问题描述

http://www.lintcode.com/en/problem/search-a-2d-matrix/

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 from left to right.
  • The first integer of each row is greater than the last integer of the previous row.

Example

Consider the following matrix:

[
    [1, 3, 5, 7],
    [10, 11, 16, 20],
    [23, 30, 34, 50]
]

Given target = 3, return true.

解题思路

题意是关于查找给定的目标值target是否在一个已经排好序的m * n的二位矩阵matrix中。如果在矩阵中找到目标值,则返回true,如果不在,则返回 false。

矩阵的特点是:

  • 每一排的数字由小到大排列
  • 每一排第一个数字都比上一排最后一个数字大

这道题是考察Binary Search二分搜索法的应用。

  • 首先,我们检查matrix是否为null或者为空。如果matrix为null或者为空,则显然找不到target,返回true。同样我们需要检查matrix中子list是否为null或者为空。因为matrix为m*n,所以只用检查第一个list即matrix[0]即可。
  • 设定排数rows = matrix.length,列数为cols = matrix[0].length。
  • 用一个for循环,对matrix每一排一一查找。
  • 在每一排的查找中,用标准的Binary Search二分搜索法进行查找target是否在该行中。若找到,则返回true。
  • 若循环结束,没有在任意一行中找到target,那么返回false。

参考代码

public class Solution { 
    /** 
     * @param matrix, a list of lists of integers 
     * @param target, an integer 
     * @return a boolean, indicate whether matrix contains target 
     */ 
    public boolean searchMatrix(int[][] matrix, int target) { 
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0 ) { 
            return false; 
        } 
         
        int row = matrix.length; 
        int col = matrix[0].length; 
         
        // search 1st column in every row 
        int start = 0; 
        int end = row - 1; 
        while (start + 1 < end) { 
            int mid = start + (end - start) / 2; 
            if (matrix[mid][0] == target) { 
                return true; 
            } else if (matrix[mid][0] < target) { 
                start = mid; 
            } else { 
                end = mid; 
            } 
        } 
         
        if (matrix[start][0] == target || matrix[end][0] == target) { 
            return true; 
        }  
         
        int possibleRow = 0; 
        if (matrix[end][0] < target) { 
            possibleRow = end; 
        } else { 
            possibleRow = start; 
        } 
         
        start = 0; 
        end = col - 1; 
        while (start + 1 < end) { 
            int mid = start + (end - start) / 2; 
            if (matrix[possibleRow][mid] == target) { 
                return true; 
            } else if (matrix[possibleRow][mid] < target) { 
                start = mid; 
            } else { 
                end = mid; 
            } 
        } 
         
        if (matrix[possibleRow][start] == target || matrix[possibleRow][end] == target) { 
            return true; 
        } 
         
        return false;         
    } 
} 

相关题目

LintCode All in One 原创题目讲解汇总

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注