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

public class Solution {
    public boolean Find(int target, int [][] array) {
        if (0 == array.length) {
            return false;
        }
        if (1 == array.length) {
            if (0 == array[0].length) {
                return false;
            }
            return array[0][0] == target ? true : false;
        }
        // 具体代码实现
        // 思路：假设这个二维数组是一个方阵，我们只需要沿着对角线找就好了
        /*
         * 如果对角线上的某个值小于target，那么就以该位置为起点，向左画一条线，向上画一条线，然后，这一部分的值的大小一定也是小于target值的。(看不懂这段话，就自己作个图，不难的)
         * 如果对角线上的某个值等于target，那么很好，直接返回true即可。
         * 如果对角线上的某个值大于target，那么就以当前位置为起点，向右画一条线，向下画一条线，然后，这两条线围成的部分就不需要再进行查找了。同时，我们一共划分出了四个区域。然后使用递归，对另外没被直线围起来的两个区域进行查找，最终返回结果。
         * 强调一下，我们假设了这个二维数组是一个方阵。非方阵的做法有一丢丢不同。
         */
        // 定义一个整型变量，用于临时存放数据
        int tmp = 0;
        // 定义一个计数器
        int acc = 0;
        
        /******************************************************************************************************/
        // 我就知道，题目没有说明，那二维数组就不一定是方阵(最后一组用例错了，报了数组越界)
        // 定义一个整型变量，用于存放二维数组一维的长度
        int il = array.length;
        // 定义一个整型变量，用于存放二维数组二维的长度
        int jl = array[0].length;
        
        // 如果是方阵，才使用下列方法
        if (il == jl) {
            // 说明一下，i 是横坐标，j 是纵坐标
            for (int i = 0, j = 0; i < il && j < jl; i++, j++) {
                tmp = array[i][j];
                if (tmp == target) {
                    // 如果等于目标值，爽歪歪，直接返回
                    return true;
                }
                else if (tmp < target) {
                    // 如果小于目标值，继续沿着对角线向右下方向进行移动
                }
                else {
                    // 如果大于目标值，那么就以当前位置为起点，向右画一条线，向下画一条线，然后，这两条线围成的部分就不需要再进行查找了。同时，我们一共划分出了四个区域。然后使用递归，对另外没被直线围起来的两个区域进行查找，最终返回结果。
                    // 好吧，递归失败了，主要是我不知道怎么用Java切割一个二维数组。那么我们换个思路，计数器的作用就是，后续的遍历，不需要一直遍历到(i, j)这个位置，只需要在(i - k, j - k)位置即可
                    for (int k = 0; k < i - acc; k++) {
                        tmp = array[i][k]; // 从左往右
                        if (tmp == target) {
                            return true;
                        }
                        tmp = array[k][j]; // 从上往下
                        if (tmp == target) {
                            return true;
                        }
                    }
                    acc++;
                }
            }
            return false;
        }
        else { // 如果是非方阵
            // 下面代码是看了某个大佬才写出来的
            // 定义两个指针
            int ip = 0;
            int jp = jl - 1;
            while (ip < il && jp >= 0) {
                tmp = array[ip][jp];
                if (tmp == target) {
                    return true;
                }
                else if (tmp < target) {
                    ip++;
                }
                else {
                    jp--;
                }
            }
            return false;
        }
    }
}