《剑指offer》二维数组中的查找

规律排列的二位数组中的查找优化

题目描述

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

思路一

将二维数组看成矩阵，从矩阵的右上角开始查找。

如果target（要查找的数）等于右上角，则return true；如果target（要查找的数）小于右上角，则剔除该列；如果target（要查找的数）大于右上角，则剔除该行；

重复上述步骤，把要查找的范围逐步缩小。

如果矩阵是n阶方阵，查找次数小于2n

解决方案一

package cn.cecurio.offer;

/**
 * @author: Cecurio
 * @create: 2017-09-04 10:55
 * @desc:
 **/
/*
测试用例1：
5,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
*/

public class ArraySearch {
    //认为数组是规则的
    public boolean find(int target, int [][] array) {
        if (array == null) {
            return false;
        }

        int rows = array.length;
        int cols = array[0].length;
        int i = 0;
        int j = cols;

        while (i < rows && j > 0) {
            if (array[i][j-1] == target) {
                return true;
            } else if (array[i][j-1] > target) {
                //target在左侧
                j--;
            } else {
                //target在右侧
                i++;
            }
        }

        return false;
    }

    public static void main(String[] args) {
        int[][] array = {
                {1,2,8,9},
                {2,4,9,12},
                {4,7,10,13},
                {6,8,11,15}
        };

        ArraySearch demo = new ArraySearch();
        boolean result = demo.find(5,array);
        System.out.println(result);
    }
}

思路二

观察到，矩阵的主对角线是递增的。

遍历主对角线上的数，需要n次

如果主对角线上的数大于target（要找的数），用二分查找去确定当前行、当前列是否包含target，如果找到，直接return true；否则，继续遍历，直到遍历完主对角线

解决方案二

import java.util.ArrayList;
import java.util.Collections;

public boolean find2(int target, int [][] array) {
        if (array == null) {
            return false;
        }

        int rows = array.length;
        int cols = array[0].length;

        if (rows == 0 || cols == 0) {
            return false;
        }

        if (array[0][0] > target || array[rows-1][cols-1] < target) {
            return false;
        }

        for (int i = 0; i < rows; i++) {
            if (array[i][i] == target) {
                return true;
            } else if (array[i][i] > target) {
                ArrayList<Integer> list1 = new ArrayList<Integer>();
                ArrayList<Integer> list2 = new ArrayList<Integer>();

                for (int j=0; j<i; j++) {
                    list1.add(array[j][i]);
                    list2.add(array[i][j]);
                }

                if (Collections.binarySearch(list1,target) >= 0 || Collections.binarySearch(list2,target) >= 0) {
                    return true;
                }

            }
        }

        return false;
    }

小结

• 把握数据的内在规律，优化代码
• 熟练使用java.util.Collections的API，简化我们的代码
• 如果有能力，掌握java.util.Collections中的算法