- 浏览: 174733 次
- 性别:
- 来自: 济南
文章分类
最新评论
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 in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.
For example,
Consider the following matrix:
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
Given target = 5, return true.
Given target = 20, return false.
在一个二维数组找一个元素,数组中的每一行和每一列都是升序排列的。我们可以从数组的右上方作者左下方的元素开始寻找。设定两个指针m, n,假设从右上方开始,如果matrix[m][n]与target相等就返回true;如果matrix[m][n]小于target就让m指针往下移动(m++); 如果大于target就让n指针向左移动(n--), 直到遍历完整个数组,这样时间复杂度为O(m+n)。代码如下:
Integers in each row are sorted in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.
For example,
Consider the following matrix:
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
Given target = 5, return true.
Given target = 20, return false.
在一个二维数组找一个元素,数组中的每一行和每一列都是升序排列的。我们可以从数组的右上方作者左下方的元素开始寻找。设定两个指针m, n,假设从右上方开始,如果matrix[m][n]与target相等就返回true;如果matrix[m][n]小于target就让m指针往下移动(m++); 如果大于target就让n指针向左移动(n--), 直到遍历完整个数组,这样时间复杂度为O(m+n)。代码如下:
public class Solution { public boolean searchMatrix(int[][] matrix, int target) { if(matrix == null || matrix.length == 0) return false; int m = 0; int n = matrix[0].length - 1; while(m < matrix.length && n >= 0) { if(matrix[m][n] == target) return true; if(matrix[m][n] > target) { n --; } else { m ++; } } return false; } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 229Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 232You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 348Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 342Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 461Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 525Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 436Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 624Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 435The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 392Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 522Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 542Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 379All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 870Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 885Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 560Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 612Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 772Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 741You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 635For a undirected graph with tre ...
相关推荐
A repo for popular coding interview problems mainly from Leetcode. 二分搜索/有序数组旋转 Find Minimum In Rotated Sorted Array Find Minimum In Rotated Sorted Array II Search In Rotated Sorted Array ...
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 ...
462 | [Minimum Moves to Equal Array Elements II](https://leetcode.com/problems/minimum-moves-to-equal-array-elements-ii/) | [C++](./C++/minimum-moves-to-equal-array-elements-ii.cpp) [Python](./Python/...
Search a 2D Matrix II 替换空格 从尾到头打印链表 重建二叉树 105. Construct Binary Tree from Preorder and Inorder Traversal 用两个栈实现队列 232. Implement Queue using Stacks 旋转数组的最小数字 153. ...
leetcode上的题目,网站上测试通过,可以借鉴下
LeetCode判断字符串是否循环 LC ...search a 2d matrix ii. 每次仅能将搜索区域缩减为之前的3/4,效率一般。从左下角或右上角扫描矩阵,时间复杂度为O(m+n)代码简单,且有较高的效率。 perfect squa
LeetCode笔记本... Search a 2D Matrix II2. Add Two Numbers50. Pow(x, n)34. First & LastPositionElementInSortedArr94. Binary Tree Inorder Traversal144. Binary Tree Preorder Traversal145. Binary 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
Search a 2D Matrix Spiral Matrix com.leetcode.list Linked List Cycle Linked List Cycle II Remove Duplicates from Sorted List com.leetcode.string Single Number com.leetcode.tree Balanced Binary Tree ...
这是我准备面试时建议的个人问题清单。... https://leetcode.com/problems/search-a-2d-matrix/ https://leetcode.com/problems/set-matrix-zeroes/ 弦乐 https://leetcode.com/problems/positions-of-large-g
A real time procedural universe, part II 354 Animating 3D characters in real time games 363 Game engine with reproducible behavior 371 Facial animation in The Getaway 378 Image compression with vector...
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
II], [39 Combination Sum], [17 Phone Num] [] BFS [] [] [] DP , [53 max subarray], , [96 DP | BST], , [] [] Binary Search , , [74 2D matrix] [] Slicing Window / Two Pointers [918 Ma
C AS THE ARRAY SIZES FOR THE 2D PROBLEM ARE NOW GETTING TOO LARGE FOR COMFORT. C INCLUDE FILES ARE NOW USED TO STREAMLINE CHANGES OF DIMENSION. C IMPLICIT DOUBLE PRECISION HAS BEEN REMOVED, AGAIN FOR ...
% setting up a GA to search for the shortest route (least distance needed % for each salesman to travel from the start location to unique % individual cities and finally to the end location) % % ...
This paper firstly, to the best of our knowledge, proposed two-dimensional (2D) encryption based on the Arnold transformation for implementing a secure DC-biased optical orthogonal time-frequency ...
2d matrix, backtracking, DP, circle array,分治法 String reverse, palindrome, Sliding window, backtracking Lists medium, reverse, merge Tree traversals, search Stack Queue Graph traversals(BFS, DFS) ...
Finish: Console.WriteLine("End of search."); foreach foreach 语句为对数组或者集合中的每个元素重复执行嵌入语句。对于数组 示例为: using System; class MainClass { public static void Main() { int odd = ...
2D Graphics Fundamentals ......................................1 3D Graphics Fundamentals ......................................3 3D Coordinate Systems and Vectors ...............................4 ...
,EAN-8,EAN-13,Code128 A,Code128 B,Code128 C,MSI,UPC-A,UPC-E. 中文转拼音库 pinyin4j Pinyin4j是一个流行的Java库,支持中文字符和拼音之间的转换。拼音输出格式可以定制。 异步HTTP客户端开发包 ...