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

二维数组中的查找

https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e

/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @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的时间空间复杂度。

#双指针##刷题心得##数组元素查找##算法刷题笔记#
全部评论

相关推荐

11-29 11:21
门头沟学院 Java
总包48.5w,意想不到的价格
想开了的垂耳兔很喜欢拱白菜:转人工
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务