剑指 Offer 04. 二维数组中的查找

【题目来源】

https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/

【题目内容】

【解题思路】

思路一：遍历(执行用时：40 ms 内存消耗：8.2 MB)

将二维数组中的每一个数字和目标数字进行比较，当发现相等时，返回true，如果一直没找到，则返回false。
时间复杂度 O(M*N)
空间复杂度 O(1)

bool findNumberIn2DArray(int** matrix, int matrixSize, int* matrixColSize, int target){
    // 遍历
    if (matrixSize == 0) {
        return false;
    }
    int colSize = matrixColSize[0];
    for (int i = 0; i < matrixSize; i++) {
        for (int j = 0; j < colSize; j++) {
            if (matrix[i][j] == target) {
                return true;
            }
        }
    }
    return false;
}

思路二：左下角查找(执行用时：32 ms 内存消耗：8.4 MB)

从左下角开始查找，如果小于目标值，则i--；如果大于目标值，则j++；如果相等，则返回true。遍历到最右侧或最上侧时，还没找到，则返回false。
思想为二叉搜索树，左下角和右上角可以做为根节点，参考：https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/solution/mian-shi-ti-04-er-wei-shu-zu-zhong-de-cha-zhao-zuo/
时间复杂度 O(M+N)
空间复杂度 O(1)

bool findNumberIn2DArray(int** matrix, int matrixSize, int* matrixColSize, int target){
    // 左下角查找
    if (matrixSize == 0) {
        return false;
    }
    int colSize = matrixColSize[0];
    int i = matrixSize - 1;
    int j = 0;
    while (i >= 0 && j <= colSize - 1) {
        if (matrix[i][j] > target) {
            i--;
            continue;
        }
        if (matrix[i][j] < target) {
            j++;
            continue;
        }
        if (matrix[i][j] == target) {
            return true;
        }
    }
    return false;
}

【学习小结】

数组比Hash性能更好

相比于HashSet，使用数组绝对会有性能的提高，主要表现在如下的两个方面：

哈希表 (HashSet) 底层是使用数组 + 链表或者红黑树组成的，而且它的数组也是用不满的，有加载因子的。所以使用数组来代替哈希表，能节省空间

哈希表在判重的时候需要经过哈希计算，还可能存在哈希冲突的情况，而使用数组则可以直接计算得到 index 的内存位置，所以使用数组访问性能更好。

链接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/solution/duo-chong-jie-fa-xun-xu-jian-jin-yi-zhi-dao-zui-yo/

调整执行顺序，性能提升

判断场景先执行nums[nums[cur]]，再执行nums[cur]，触发预取，提高性能。

将满足条件概率更大的条件放到前面，可以避免大量无效判断，提高性能。

剑指 Offer