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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param target int整型 
 * @param array int整型二维数组 
 * @param arrayRowLen int array数组行数
 * @param arrayColLen int* array数组列数
 * @return bool布尔型
 */
bool Find(int target, int** array, int arrayRowLen, int* arrayColLen ) {
    // write code here
    if(arrayRowLen <= 0 || (*arrayColLen) <= 0) //矩阵为空矩阵，直接返回false
        return false;
    
    int row = 0, col = *arrayColLen - 1;  //使用双指针，定义行列指针,f初始时分别指向第0行和最后一列
    while(row < arrayRowLen && col >= 0)
    {
        if(array[row][col] == target)
        {
            return true;
        }
        else if(array[row][col] > target)   //如果当前元素大于目标值，col左移
        {
            col--;
        }
        else if(array[row][col] < target)   //如果当前元素大于目标值，row下移一行，col不变，因为后面的列必定大于target
        {
            row++;
        }

    }

    return false;;
}

本题是数组中元素查找问题。无论是字符串还是数字数组，无论是一维数组还是二维数组，遇到数组元素查找问题，无论返回元素值、索引还是true或者false,首先考虑双指针，双指针又包括二分查找、滑动窗口，前者用于查找某一具体给定目标，后者用于解决子串问题。显然本题是查找目标问题，因此使用双指针，但是又不是使用标准的二分查找，有点像和滑动窗口结合，利用行列的单调递增规律不断收缩查找范围，最终实现n+m和1的时间空间复杂度。