力扣网C语言编程题：搜索二维矩阵（右上角-＞左下角解法）

一. 简介

上一篇文章关于"在二维数组中查找某个元素"的问题，提供了两种解题思路，文章如下：

力扣网C语言编程题：搜索二维矩阵的普通解法与二分查找法-CSDN博客

本文提供第三种解题思路：从左下角->右上角，或者右上角->左下角。

二.力扣网C语言编程题：搜索二维矩阵（右上角->左下角解法）

 解题思路三：（换行或换列）

因为题目中，数组中元素是每行元素是递增的，同时，每一行的首元素比上一行最后一个元素大，那么，这个二维数组中的每一列的元素也是递增的。(可以画一个二维元素的框图来理一下逻辑)

可以从右上角开始查找元素：

如果 nums[i][j] == target，则直接返回 true。

如果 nums[i][j] > target，根据列元素递增，则说明该列所有元素都是大于 target，丢弃该列，j--。

如果 nums[i][j] < target，根据行元素也是递增的，则说明该行所有元素都是小于 target，丢弃改行，i++。

C语言实现如下：

bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target) {
    int m = matrixSize;
    int n = matrixColSize[0];
    int i = 0;
    int j = n-1;

    while((i < m) && (j >= 0)) {
        if(matrix[i][j] == target) {
            return true;
        }
        else if(matrix[i][j] < target) {
        //说明该行所有元素都小于 target,换下一行
            i++;
        }
        else {
        //matrix[i][j] > target,说明该列所有元素都大于target,换上一列
            j--;
        }
    }   
    return false;
}

可以看出，这种方法的时间复杂为 O(m+n)。

也可以从左下角开始向右上角搜索，C语言实现如下：

//从左下角到右上角进行查找
bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target) {
    int row = matrixSize;
    int col = matrixColSize[0];
    int i = row-1;
    int j = 0;

    while((i >= 0) && (j < col)) {
        if(matrix[i][j] == target) {
            return true;
        }
        else if(matrix[i][j] > target) {
        //说明该行所有元素都大于target,则跳到上一行
            i--;
        }
        else {
        //matrix[i][j]<target,说明该列所有元素都小于target
        //跳到下一列
            j++;
        }
    }   

    return false;
}

上面的实现思路其实和从右上角->左下角的方法是类似的。