C++实现LeetCode(74.搜索一个二维矩阵)

[LeetCode] 74. Search a 2D Matrix 搜索一个二维矩阵

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

  • Integers in each row are sorted from left to right.
  • The first integer of each row is greater than the last integer of the previous row.

Example 1:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Example 2:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

Constraints:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 100
  • -104 <= matrix[i][j], target <= 104

这道题要求搜索一个二维矩阵,由于给的矩阵是有序的,所以很自然的想到要用二分查找法,可以在第一列上先用一次二分查找法找到目标值所在的行的位置,然后在该行上再用一次二分查找法来找是否存在目标值。对于第一个二分查找,由于第一列的数中可能没有 target 值,该如何查找呢,如果是查找第一个不小于目标值的数,当 target 在第一列时,会返回 target 所在的行,但若 target 不在的话,有可能会返回下一行,不好统一。所以可以查找第一个大于目标值的数,也就是总结帖中的第三类,这样只要回退一个,就一定是 target 所在的行。但需要注意的一点是,如果返回的是0,就不能回退了,以免越界,记得要判断一下。找到了 target 所在的行数,就可以再次使用二分搜索,此时就是总结帖中的第一类了,查找和 target 值相同的数,也是最简单的一类,分分钟搞定即可,参见代码如下:

解法一:

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) return false;
        int left = 0, right = matrix.size();
        while (left < right) {
            int mid = (left + right) / 2;
            if (matrix[mid][0] == target) return true;
            if (matrix[mid][0] < target) left = mid + 1;
            else right = mid;
        }
        int tmp = (right > 0) ? (right - 1) : right;
        left = 0;
        right = matrix[tmp].size();
        while (left < right) {
            int mid = (left + right) / 2;
            if (matrix[tmp][mid] == target) return true;
            if (matrix[tmp][mid] < target) left = mid + 1;
            else right = mid;
        }
        return false;
    }
};

当然这道题也可以使用一次二分查找法,如果我们按S型遍历该二维数组,可以得到一个有序的一维数组,只需要用一次二分查找法,而关键就在于坐标的转换,如何把二维坐标和一维坐标转换是关键点,把一个长度为n的一维数组转化为 m*n 的二维数组 (m*n = n)后,那么原一维数组中下标为i的元素将出现在二维数组中的 [i/n][i%n] 的位置,有了这一点,代码很好写出来了:

解法二:

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) return false;
        int m = matrix.size(), n = matrix[0].size();
        int left = 0, right = m * n;
        while (left < right) {
            int mid = (left + right) / 2;
            if (matrix[mid / n][mid % n] == target) return true;
            if (matrix[mid / n][mid % n] < target) left = mid + 1;
            else right = mid;
        }
        return false;
    }
};

这道题其实也可以不用二分搜索法,直接使用双指针也是可以的,i指向0,j指向列数,这样第一个被验证的数就是二维数组右上角的数字,假如这个数字等于 target,直接返回 true;若大于 target,说明要减小数字,则列数j自减1;若小于 target,说明要增加数字,行数i自增1。若 while 循环退出了还是没找到 target,直接返回 false 即可,参见代码如下:

解法三:

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

到此这篇关于C++实现LeetCode(74.搜索一个二维矩阵)的文章就介绍到这了,更多相关C++实现搜索一个二维矩阵内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C++实现LeetCode(66.加一运算)

    [LeetCode] 66. Plus One 加一运算 Given a non-empty array of decimal digits representing a non-negative integer, increment one to the integer. The digits are stored such that the most significant digit is at the head of the list, and each element in the a

  • C++实现LeetCode(68.文本左右对齐)

    [LeetCode] 68.Text Justification 文本左右对齐 Given an array of words and a width maxWidth, format the text such that each line has exactly maxWidth characters and is fully (left and right) justified. You should pack your words in a greedy approach; that i

  • C++实现LeetCode(64.最小路径和)

    [LeetCode] 64. Minimum Path Sum 最小路径和 Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. Note: You can only move either down or right at any point in t

  • C++实现LeetCode(73.矩阵赋零)

    [LeetCode] 73.Set Matrix Zeroes 矩阵赋零 Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place. click to show follow up. Follow up: Did you use extra space? A straight forward solution using O(mn) space is probably

  • C++实现LeetCode(63.不同的路径之二)

    [LeetCode] 63. Unique Paths II 不同的路径之二 A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right c

  • C++实现LeetCode(67.二进制数相加)

    [LeetCode] 67. Add Binary 二进制数相加 Given two binary strings a and b, return their sum as a binary string. Example 1: Input: a = "11", b = "1" Output: "100" Example 2: Input: a = "1010", b = "1011" Output: &q

  • C++实现LeetCode( 69.求平方根)

    [LeetCode] 69. Sqrt(x) 求平方根 Implement int sqrt(int x). Compute and return the square root of x, where x is guaranteed to be a non-negative integer. Since the return type is an integer, the decimal digits are truncated and only the integer part of the

  • C++实现LeetCode(174.地牢游戏)

    [LeetCode] 174. Dungeon Game 地牢游戏 The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the t

  • C++实现LeetCode(74.搜索一个二维矩阵)

    [LeetCode] 74. Search a 2D Matrix 搜索一个二维矩阵 Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties: Integers in each row are sorted from left to right. The first integer of each row is great

  • PHP实现一个二维码同时支持支付宝和微信支付的示例

    实现思路 生成一个二维码,加入要处理的url连接 在用户扫完码后,在对应的脚本中,判断扫码终端,调用相应的支付 若能够扫码之后能唤起相应app,支付宝要用手机网站支付方式,微信要使用jsapi支付方式 效果展示 提示: 因为项目即将上线,所以上面的支付二维码连接被我替换了(注意在生成二维码时加入的连接,要带上http协议) 实现 步骤生成二维码 //我的url指向了checkTerrace方法 $url = self::ADMIN_URL . 'params=' . $params; //ADM

  • 基于PyQT5制作一个二维码生成器

    个性化二维码的exe桌面应用的获取方式我放在文章最后面了,注意查收.通过执行打包后的exe应用程序可以直接运行生成个性化二维码. 开始之前先来看一下通过二维码生成器是如何生成个性化二维码的. 其中使用的python包和之前的GUI应用制作使用的模块是一样的. # -*- coding:utf-8 -*- import os import sys from PyQt5.QtWidgets import * from PyQt5.QtGui import * from PyQt5.QtCore im

  • 基于Python编写一个二维码生成器

    目录 前言 1.安装第三方库 2.QRCode参数解释 3.自定义二维码生成器 4.给二维码加图片 5.全部代码 前言 二维码又称二维条码,常见的二维码为QR Code,QR全称Quick Response,是一个近几年来移动设备上超流行的一种编码方式,它比传统的Bar Code条形码能存更多的信息,也能表示更多的数据类型.现在的二维码随处可见,甚至有人觉得在以后的墓碑上都可以刻一个二维码,通过扫描该二维码便可知墓主传奇的一生.所以如何快速定制自己的二维码便显得极为的重要,本文用python生成

  • java高效打印一个二维数组的实例(不用递归,不用两个for循环)

    打印1个元素,不让循环变量i++,走出思维定式(执行一次循环体,就i++).public class OneForPrint2DArr { public static void main(String[] args) throws Exception { int[][] a = { { 1, 2, 3 }, { 4, 5} }; for (int i = 0, j = 0; i < a.length;) { System.out.println(a[i][j]); j++; if (j >=

  • 利用Javascript开发一个二维周视图日历

    前言 本文给大家介绍了Javascript开发二维周视图日历的相关内容,即之前实现了一个月视图日历,我们今天来实现一个二维周视图的日历. 以下进行分析其中的关键部分. 结构准备 不同之处在于其在日历的基础上还有一个分类轴,用于展示不同的类目,主要用于一周内的日程安排.会议安排等. 二维则和之前单独的有所不同,二维日历再切换日期时不用全部重新渲染,分类是不用变的,仅仅改变显示的日期即可. 而且由于是二维的,插入的内容必定是同时属于一个分类和一个时间段的,内容肯定是可以跨越时间(即日期轴)的,因此不

  • python+numpy按行求一个二维数组的最大值方法

    问题描述: 给定一个二维数组,求每一行的最大值 返回一个列向量 如: 给定数组[1,2,3:4,5,3] 返回[3:5] import numpy as np x = np.array([[1,2,3],[4,5,3]]) # 先求每行最大值得下标 index_max = np.argmax(x, axis=1)# 其中,axis=1表示按行计算 print(index_max.shape) max = x[range(x.shape[0]), index_max] print(max) # 注

  • JS实现简单的二维矩阵乘积运算

    本文实例讲述了JS实现简单的二维矩阵乘积运算方法.分享给大家供大家参考,具体如下: Console控制台截图如下: (上图为输出结果直接上代码了(A矩阵可以乘以B矩阵的前提是A矩阵的列数等于B矩阵的行数) <!DOCTYPE html> <html> <head> <title>demo</title> </head> <body> </body> <script type="text/java

  • Python获取二维矩阵每列最大值的方法

    因为做项目中间有一个很小的环节需要这个功能,所以就写了一个简单的小函数,下面是具体实现: #!usr/bin/env python #encoding:utf-8 ''' __Author__:沂水寒城 ''' def get_max_value(martix): ''' 得到矩阵中每一列最大的值 ''' res_list=[] for j in range(len(martix[0])): one_list=[] for i in range(len(martix)): one_list.ap

  • python 二维矩阵转三维矩阵示例

    如下所示: >>> import numpy as np >>> a = np.arange(12).reshape(3,4) >>> a array([[ 0, 1, 2, 3], [ 4, 5, 6, 7], [ 8, 9, 10, 11]]) >>> type(a) <class 'numpy.ndarray'> >>> b=np.reshape(a,(3,4,1)) >>> np

随机推荐