剑指offer题解合集——Week1day3

剑指offerWeek1

周三：二维数组中的查找

题目链接：二维数组中的查找

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。

请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

数据范围
二维数组中元素个数范围 [0,1000]
样例
输入数组：

[
  [1,2,8,9]，
  [2,4,9,12]，
  [4,7,10,13]，
  [6,8,11,15]
]

如果输入查找数值为7，则返回true，

如果输入查找数值为5，则返回false。

AC代码

class Solution {
public:
    bool searchArray(vector<vector<int>> array, int target) {
        if (array.empty() || array[0].empty()) return false;
        int i = 0, j = array[0].size() - 1;
        
        while (i < array.size() && j >= 0)
        {
            int t = array[i][j];
            if (t == target) return true;
            if (t > target) j -- ;
            else i ++ ;
        }
        
        return false;
    }
};

思路：

整体思路

本题可以借鉴游戏：俄罗斯方块来理解
在俄罗斯方块中：当一行都有方块时，则消除该行
抽象一层，即：满足某个性质，消除一行

本题中，题目直接给出性质：每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
那么可以利用性质，给出如下思路
对于目标值x，每次都和第一行的最后一个数值进行判断

如果目标值x大于第一行的最后一个数值，则说明，第一行的所有数值都小于目标值x，则消除第一行
若目标值x小于第一行的最后一个数值，则说明，第一列的所有数值都大于目标值x，则消除第一列
如此，不断往复，并且在往复的过程中判断是否是目标值即可

代码思路

• 特判，数值是否为空
• 确定行列值
• while循环，循环条件是二维数组中还存在数值
  • 如果目标值x大于第一行的最后一个数值，则说明，第一行的所有数值都小于目标值x，则消除第一行，i++
  • 若目标值x小于第一行的最后一个数值，则说明，第一列的所有数值都大于目标值x，则消除第一列，j –
  • 如果是目标值，则直接返回true
• 若循环结束都没有找到，则返回false

部分模拟

[
[1,2,8,9]，
[2,4,9,12]，
[4,7,10,13]，
[6,8,11,15]
]

如果输入查找数值为7

• 数组存在

• 从第一行第四列开始，i = 0，j = 3

• while循环，循环条件是二维数组中还存在数值

  • 第一行第四列数值为9
    • 大于目标值7，则第四列的数值都大于目标值7，第四列直接舍去，j –
    • 此时二维数组为

  [
    [1,2,8]，
    [2,4,9]，
    [4,7,10]，
    [6,8,11]
  ]
  

  • 第一行第三列数值为8
    • 大于目标值7，则第三列的数值都大于目标值7，第三列直接舍去，j –
    • 此时二维数组为

  [
    [1,2]，
    [2,4]，
    [4,7]，
    [6,8]
  ]
  

  • 第一行第二列数值为2
    • 小于目标值7，则第一行的数值都小于于目标值7，第一行直接舍去，i++
    • 此时二维数组为

  [
    [2,4]，
    [4,7]，
    [6,8]
  ]
  

  • 如此往复即可