题解 | #二维数组中的查找#

最简单的方法就是遍历，时间复杂度为O(n^2)。

考虑到数组从左到右，从上到下逐渐增多，即，每一行最右侧的元素是该行最大，每一列最下侧的元素是该列最大。

利用这个特性，可以作为过滤条件，筛选数据，减少比较次数。

这里考虑每次和当前行最右侧的元素进行比较。如果小于，那么就在左侧的那些列中；如果大于，那就在下几行中。也就是说，这样比较的话，每次都可以过滤到一行或一列。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param target int整型 
     * @param array int整型二维数组 
     * @return bool布尔型
     */
    public boolean Find (int target, int[][] array) {
        // write code here
        // 和右上角比较
        if (array == null) {
            return false;
        }
        int row = array.length, col = array[0].length;
        if (row == 0 || col == 0) {
            return false;
        }
        if (target < array[0][0] || target > array[row - 1][col - 1]) {
            return false;
        }
        int i = 0, j = col - 1;
        while (i < row && j >= 0) {
            if (target == array[i][j]) {
                return true;
            } else if (target < array[i][j]) {
                // 小于右上角，则在左侧
                j = j - 1;
            } else {
                // 大于右上角，则在下侧
                i = i + 1;
            }
        }
        return false;
    }
}