剑指offer_数组---二维数组中的查找

题目描述

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

解题思路

1，直接用hashset
2，用技巧方法，依据递增顺序这一特点

代码实现

package 数组;

import java.util.HashSet;

/** * * * 在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。 * 请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。 */
public class Find {

    public static void main(String[] args) {

        int[][] arrays = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
        System.out.println(new Find().BoolFindSuper(11, arrays));

    }

    // ==============================================================非技巧解法，利用set判断
    public boolean BoolFind(int target, int[][] array) {
        HashSet<Integer> set = new HashSet<Integer>();
        if (array == null || array.length < 1) {
            return false;
        }
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array[i].length; j++) {
                set.add(array[i][j]);
            }
        }
        if (set.contains(target)) {
            return true;
        }
        return false;

    }

    // ==============================================================技巧解法，利用set判断
    public boolean BoolFindSuper(int target, int[][] array) {
        if (array == null || array.length < 1) {
            return false;
        }
        for (int i = 0, j = array[0].length - 1; i < array.length && j >= 0;) {
            int num = array[i][j]; // 让初始值为右上角
            if (target == num) {
                return true;
            } else if (target < num) {    //如果目标值小于当前值，向左搜索
                j--;
                continue;
            } else {
                i++;
                continue;                //如果目标值大于当前值，向右搜索
            }
        }

        return false;

    }
}