美文网首页
240、搜索二维矩阵 II | 算法(leetcode,附思维导

240、搜索二维矩阵 II | 算法(leetcode,附思维导

作者: 码农三少 | 来源:发表于2022-07-30 19:30 被阅读0次

    零 标题:算法(leetcode,附思维导图 + 全部解法)300题之(240)搜索二维矩阵 II

    一 题目描述

    题目描述
    题目描述
    题目描述

    二 解法总览(思维导图)

    思维导图

    三 全部解法

    面试官:题目看得差不多了吧,怎么样、有无思路呀?

    狂徒张三:涉及“映射、数量、重复性(即去重)、唯一性(即次数)等”,我可能会优先考虑hash(JS里对应的是 map数据结构)。

    面试官:那你先讲讲大致思路吧

    狂徒张三:

    1)遍历二维数组里的每个元素,将它们放在哈希表里。
    2)最后判断 target 值,是否在哈希表里即可~
    

    面试官:嗯嗯,整体思路是ok的,那么开始写吧

    狂徒张三:过了2分52秒后,张三就写完了程序

    1 方案1

    1)代码:

    // 方案1 “自己。哈希法”。
    // 注:通过 124 / 129,会超时。
    // 用时:15:14 - 15:16。
    // 技巧:涉及“映射、数量、重复性(即去重)、唯一性(即次数)等”可优先考虑hash(JS里对应的是 map数据结构)。
    
    // 思路:
    // 1)状态初始化:m = matrix.length, n = matrix[0].length;
    // resMap = new Map();
    // 2)遍历二维数组,将每个元素放入 resMap 中。
    // 3)返回结果: resMap.has(target) 。
    var searchMatrix = function(matrix, target) {
        // 1)状态初始化:m = matrix.length, n = matrix[0].length;
        // resMap = new Map();
        const m = matrix.length,
            n = matrix[0].length;
        let resMap = new Map();
    
        // 2)遍历二维数组,将每个元素放入 resMap 中。
        for (let i = 0; i < m; i++) {
            for (let j = 0; j < n; j++) {
                const tempVal = matrix[i][j];
                resMap.set(tempVal, 1);
            }
        }
    
        // 3)返回结果: resMap.has(target) 。
        return resMap.has(target);
    };
    

    旁边:代码在后台运行中,过了3秒,屏幕突然【闪现】出【通过 124 / 129,超出时间限制】。

    面试官(面带一丝轻蔑):小伙子,写代码要讲武德、要善于利用题干的条件

    狂徒张三(定睛细看题干60秒后):嗯嗯,有序,emmmm ---> 是否可以使用二分查找呢?

    面试官:你仔细想想哈

    狂徒张三(脑离回想二分查找的各种思路、模板后):整体思路如下:

    1)遍历二维数组的每一行,对每一行(即有序数组)使用二分查找 —— 判断 target 是否在里面。
    2)若 每一行都不存在 target 值,则 返回 false ,否则返回 true 。
    

    面试官:


    image.png

    旁白:几分钟不到,张三就写完了 “二分查找”法 的代码并通过了所有的case。

    2 方案2

    1)代码:

    // 方案2 “自己。二分查找”。
    // 用时:15:37 - 15:43。
    // 技巧:在有序的数组里进行元素的查找,可优先考虑“二分查找”。
    
    // 思路:
    // 1)状态初始化:m = matrix.length, n = matrix[0].length;
    // resFlag = false; 。
    // 2)核心:遍历二维数组的每一行,对每一行(即有序数组)使用二分查找 —— 判断 target 是否在里面。
    // 2.1)若 target 在当前行 —— isFindTarget(matrix[i], target),
    // 则 resFlag = true 并退出搜索。
    // 3)返回结果: resFlag 。
    var searchMatrix = function(matrix, target) {
        const isFindTarget = (list = [], target = 0) => {
            const l = list.length;
            let left = 0,
                right = l - 1,
                resFlag = false;
    
            while (left <= right) {
                const mid = left + Math.floor((right - left) / 2),
                    midVal = list[mid];
    
                if (midVal === target) {
                    resFlag = true;
                    break;
                }
                else if (midVal > target) {
                    right = mid - 1;
                }
                else {
                    left = mid + 1;
                }
            }
    
            return resFlag;
        };
    
        // 1)状态初始化:m = matrix.length, n = matrix[0].length;
        // resFlag = false; 。
        const m = matrix.length,
            n = matrix[0].length;
        let resFlag = false;
    
        // 2)核心:遍历二维数组的每一行,对每一行(即有序数组)使用二分查找 —— 判断 target 是否在里面。
        for (let i = 0; i < m; i++) {
            // 2.1)若 target 在当前行 —— isFindTarget(matrix[i], target),
            // 则 resFlag = true 并退出搜索。
            if (isFindTarget(matrix[i], target)) {
                resFlag = true;
                break;
            }
        }
    
        // 3)返回结果: resFlag 。
        return resFlag;
    }
    

    面试官:仔细看题干 —— “每行的元素从左到右升序排列。每列的元素从上到下升序排列。”,那么我们是否从一些特殊的位置开始搜索呢?

    狂徒张三(仔细看了看):嗯嗯,看起来左下角、右上角是比较靠中间的元素,我们可以从它们开始搜索。

    面试官:


    image.png

    狂徒张三:

    比如,
    1)我们从左下角开始不断【向上、向右】搜索。
    1.1)若 当前值 tempVal === target,则 退出搜索。
    1.2)若 当前值 tempVal < target,则 向右搜索。
    1.3)若 当前值 tempVal > target,则 向上搜索。
    

    面试官:


    image.png

    3 方案3

    1)代码:

    // 方案3 “自己。Z 字形查找”。
    // 用时:15:22 - 15:27。
    
    // 想法:
    // 1)题干中,“每行的元素从左到右升序排列。每列的元素从上到下升序排列。”。
    // 2)那么我们开始选择较为中间的位置开始搜索,若当前值偏小就向右搜索、偏大就向上搜索、相等就退出搜索。
    
    // 思路:
    // 1)状态初始化:m = matrix.length, n = matrix[0].length;
    // i = m - 1, j = 0【从左下角开始搜索】, resFlag = true;
    
    // 2)核心:从左下角开始不断【向上、向右】搜索。
    // 2.1)若 当前值 tempVal === target,则 退出搜索。
    // 2.2)若 当前值 tempVal < target,则 向右搜索。
    // 2.2)若 当前值 tempVal > target,则 向上搜索。
    
    // 3)返回结果 resFlag 。
    var searchMatrix = function(matrix, target) {
        // 1)状态初始化:m = matrix.length, n = matrix[0].length;
        // i = m - 1, j = 0【从左下角开始搜索】, resFlag = true;
        const m = matrix.length,
            n = matrix[0].length;
        let i = m - 1,
            j = 0,
            resFlag = true;
    
        // 2)核心:从左下角开始不断【向上、向右】搜索。
        while (true) {
            if (i < 0 || i >= m || j < 0 || j >= n) {
                resFlag = false;
                break;
            }
    
            const tempVal = matrix[i][j];
            // 2.1)若 当前值 tempVal === target,则 退出搜索。
            if (tempVal === target) {
                break;
            }
            // 2.2)若 当前值 tempVal < target,则 向右搜索。
            else if (tempVal < target) {
                j++;
            }
            // 2.2)若 当前值 tempVal > target,则 向上搜索。
            else {
                i--;
            }
        }
    
        // 3)返回结果 resFlag 。
        return resFlag;
    };
    

    旁白:张三写完了如上代码,急忙问面试官。

    狂徒张三:通过面试了吧?

    面试官:


    image.png

    狂徒张三:


    image.png

    又1个offer,然后马上就要出任 CEO 了,我晚上应该是去吃 沙县小吃 呢? 还是 兰州拉面 呢?哎,选择太多也是一种烦恼!

    四 资源分享 & 更多

    1 历史文章 - 总览

    历史文章 - 总览 历史文章 - 总览 刷题进度 - LeetCode:578 / 2722 、《剑指offer》:66 / 66

    2 博主简介

    码农三少 ,一个致力于编写 极简、但齐全题解(算法) 的博主。
    专注于 一题多解、结构化思维 ,欢迎一起刷穿 LeetCode ~

    相关文章

      网友评论

          本文标题:240、搜索二维矩阵 II | 算法(leetcode,附思维导

          本文链接:https://www.haomeiwen.com/subject/psbdirtx.html