原题
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
- 每行中的整数从左到右按升序排列。
- 每行的第一个整数大于前一行的最后一个整数。
示例1:
输入: matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 3 输出: true
示例2:
输入: matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 13 输出: false
解法
思想
先进行行的二分搜索，找出在哪一行之后再对列进行二分搜索。
代码
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix.length == 0||matrix[0].length==0) return false;
int start = 0;
int end = matrix.length-1;
int width = matrix[0].length-1;
while(start<end){
int mid = (start+end)/2;
if(matrix[mid][width]==target) return true;
else if(matrix[mid][width]>target) end = mid;
else start = mid+1;
}
int row = start;
start = 0;
end = width;
while(start<end){
int mid = (start+end)/2;
if(matrix[row][mid]==target) return true;
else if(matrix[row][mid]>target) end = mid-1;
else start = mid+1;
}
if(matrix[row][start]!=target) return false;
return true;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode74-%e6%90%9c%e7%b4%a2%e4%ba%8c%e7%bb%b4%e7%9f%a9%e9%98%b5/
相关推荐
-
剑指offer40-最小的k个数
原题（来源Leetcode） 输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。 示例 1： ...
-
leetcode1071-字符串的最大公因子
原题 对于字符串 S 和 T，只有在 S = T + ... + T（T 与自身连接 1 次或多次）时，我们才认定 “T 能除尽 S”。 返回最长字符串 X，要求满足 X 能除尽 ...
-
leetcode707-设计链表
原题 设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用...
-
leetcode283-移动零
原题 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。 示例: 输入: [0,1,0,3,12] 输出: [1,3,12,0,0] 说...
-
leetcode63-不同路径II
原题 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Fi...
-
leetcode162-寻找峰值
原题 峰值元素是指其值大于左右相邻值的元素。 给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。 数组可能包含多个峰值，在这种情况...
-
二叉树中序遍历-折纸问题
原题（来源牛客网） 请把纸条竖着放在桌⼦上，然后从纸条的下边向上⽅对折，压出折痕后再展开。此时有1条折痕，突起的⽅向指向纸条的背⾯，这条折痕叫做“下”折痕 ；突起的⽅向指向纸条正⾯...
-
leetcode876-链表的中间结点
原题 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。 如果有两个中间结点，则返回第二个中间结点。 示例 1: 输入： [1,2,3,4,5] 输出： 此列表中的结...
-
leetcode263-丑数
原题 编写一个程序判断给定的数是否为丑数。 丑数就是只包含质因数 2, 3, 5 的正整数。 示例1: 输入： 6 输出： true 解释： 6 = 2 × 3 示例2: 输入： ...
-
leetcode26-删除排序数组中的重复项
原题 给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。 不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空...
