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

问题描述

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

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

解题思路

题意是关于查找给定的目标值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 原创题目讲解汇总