[数据结构与算法] LeetCode

编写一个高效的算法来判断?m x n?矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。

示例1：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3

输出：true
示例2：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13

输出：false

题目分析😉

? ? ?由于每行中的整数从左到右按升序排列且每行的第一个整数大于前一行的最后一个整数，其实就意味着整个矩阵的数据都是升序排列的，只是分为了矩阵而已。按照这种特性我们先需要遍历矩阵中最后一列的数据，如果这一列数据比目标值target大，即在要查找数据肯定在这一行，那么只需要遍历这一行数据即可。

? ? ?其实发现最后一列的数据也是升序排列的，而每一行也是升序排列的，那么意味着我们在遍历最后一列和某一行数据时可以采用二分查找的方法，但最后要查找的数是在某一行出现的，所以在遍历行时采用二分查找的方法。

函数参数分析：

? ? ?一般开辟的二维数组传参都是直接将首行地址数组地址传过来，用数组指针来接收。可以看见这里的接收二维数组是一个二级指针，其实这个二维数组是在堆区用malloc开辟的。先开辟一个存地址的数组，然后在开辟很多数组，把这些数组的首地址存起来，即构成了一个二维数组。在释放时，也要先释放parr这块的数组，然后再释放pparr。（后面有代码实现）matrixSize就是矩阵的行数，matrixColSize是矩阵列数的地址，target就是要查找的目标数。

代码实现（顺序查找法）

bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target)
{
    int row = matrixSize;
    int col = *matrixColSize;
    int i = 0;
    for (i = 0; i < row; i++)
    {
        if (matrix[i][col - 1] > target || matrix[i][col - 1] == target)
        {
            break;
        }
    }
    //for循环跳出，修正下标
    if (i == row)
    {
        i -= 1;
    }
    int j = 0;
    for (j = 0; j < col; j++)
    {
        if (matrix[i][j] == target)
        {
            return true;
        }
    }
    return false;
}

?代码实现（二分查找法）

bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target)
{
    int row = matrixSize;
    int col = *matrixColSize;
    int i = 0;
    //找需要找目标值的行
    for (i = 0; i < row; i++)
    {
        if (matrix[i][col - 1] > target || matrix[i][col - 1] == target)
        {
            break;
        }
    }
    //for循环跳出，修正下标
    if (i == row)
    {
        i -= 1;
    }
    int left = 0;
    int right = col - 1;
    while (left <= right)
    {
        int mid = (left + right) >> 1;
        if (matrix[i][mid] > target)
        {
            right = mid - 1;
        }
        else if (matrix[i][mid] == target)
        {
            return true;
        }
        else
        {
            left = mid + 1;
        }
    }
    //while循环跳出则找不到目标值
    return false;
}

代码实现（二维数组在堆区开辟）

int main()
{
    //保存地址的数组
    int** pa = (int**)malloc(sizeof(int) * 3);
    int i = 0;
    int col = 3;
    //将数组地址都存pa中
    for (i = 0; i < 3; i++)
    {
        pa[i] = (int*)malloc(sizeof(int) * col);
    }


    for (i = 0; i < 3; i++)
    {
        free(pa[i]);
    }
    free(pa);
    return 0;
}