Search a 2D Matrix
来自 <https://leetcode.com/problems/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.
For example,
Consider the following matrix:
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
Given target = 3, return true.
题目解读
写一个能够从m x n 的矩阵中找出特定值的高校算法,这个矩阵有以下特点
- 每一行的整数从左到右为有序的
- 每一行的第一个数比上一行的最后一个数大。
例如
考虑如下矩阵
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
给定target=3, 返回true.
解析一:
最直接的方法就是从前往后,从左到右进行遍历整个数组,时间复杂度为O(mn).
解析二:
由于给定的矩阵从左到右,从上到下都是有序的,所以可以首先考虑到二分查找,首先找到target大致在哪一行,然后找出其确定位置。
解析一代码(略)
解法二代码
public class Solution { public boolean searchMatrix(int[][] matrix, int target) { int low = 0; int high = matrix.length-1; int mid = (low + high) / 2; /** * 二分查找target大致在哪一行 */ while(low<=high) { mid = (low + high) / 2; if( matrix[mid][0] == target) return true; else if (matrix[mid][0] < target) low = mid+1; else high = mid-1; } //target所在的行是low和high中小的那个 int row = (low+high) / 2; low = 0; high = matrix[mid].length-1; /** * 二分查找target所在的具体位置 */ while(low<=high) { mid = (low + high) / 2; if( matrix[row][mid] == target) return true; else if (matrix[row][mid] < target) low = mid+1; else high = mid-1; } return false; } }
解法二性能
相关推荐
leetcode上的题目,网站上测试通过,可以借鉴下
leetcode 答案leetcode-java leetcode.com 的 Java 答案 ================索引================ com.leetcode.array Search a 2D Matrix Spiral Matrix com.leetcode.list Linked List Cycle Linked List Cycle II ...
Search a 2D Matrix I240. Search a 2D Matrix II2. Add Two Numbers50. Pow(x, n)34. First & LastPositionElementInSortedArr94. Binary Tree Inorder Traversal144. Binary Tree Preorder Traversal145. Binary ...
* [Binary Search Tree](https://github.com/kamyu104/LeetCode#binary-search-tree) * [Breadth-First Search](https://github.com/kamyu104/LeetCode#breadth-first-search) * [Depth-First Search]...
Leetcode扑克 项目简介 该项目为《剑指Offer》题解 OnlineJudge 题目 个人建议能使用LeetCode还是尽量用LeetCode。因为LeetCode题目接口更为规范,而且测试数据也更为全面。 牛客网 LeetCode 二维数组中的查找 240. ...
这是我准备面试时建议的个人问题清单。... https://leetcode.com/problems/search-a-2d-matrix/ https://leetcode.com/problems/set-matrix-zeroes/ 弦乐 https://leetcode.com/problems/positions-of-large-g
1、题目详解 ...https://leetcode-cn.com/problems/search-a-2d-matrix-ii/solution/er-fen-fa-pai-chu-fa-python-dai-ma-java-dai-ma-by-/ 2、代码详解 # -*- coding:utf-8 -*- class Solution: # arr
leetcode 2 Useful Links 我的题解 刷题打卡活动 算法基础课 算法基础课笔记 基础算法 : 快速排序,归并排序 : 整数二分,浮点数二分 数据结构 搜索与图论 : Dijkstra, Bellman-Ford, SPFA, Floyd : 染色法、匈牙利...
leetcode 社交面试准备 问题类别: Array 二ptr/sliding window, 2d matrix, backtracking, DP, circle array,分治法 String reverse, palindrome, Sliding window, backtracking Lists medium, reverse, merge Tree...
1. Introduction 2. Array i. Remove Element ii. Remove Duplicates from Sorted Array iii.... Search a 2D Matrix xii. Search for a Range xiii. Search Insert Position xiv. Find Peak Element
leetcode Coding-Interview A repo for popular coding interview problems mainly from Leetcode. 二分搜索/有序数组旋转 Find Minimum In Rotated Sorted Array Find Minimum In Rotated Sorted Array II Search ...
LeetCode判断字符串是否循环 LC 算法练习 LeetCode需要重点关注的题目 简单题型 中等难度题型 kth largest element in an array . use heap, use quick select. maximal square. Use dynamic programming. use just ...
Search a 2D Matrix II Find Minimum in Rotated Sorted Array Find Minimum in Rotated Sorted Array II Median of Two Sorted Arrays H-Index II 暴力枚举法 Subsets Subsets II Permutations Permutations II ...