问题描述:
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
.
原问题链接:https://leetcode.com/problems/search-a-2d-matrix/
问题分析
Young tableaus
这个问题有好几种思路可以解决。一种方法在之前的文章里也有讨论过。这种方法就是基于young tableaus来做的。就是在开始的时候从矩阵的右上角开始。每次用目标元素和这个位置的元素进行比较,如果目标元素比这个值小,则列值减一,如果目标元素比这个元素大,则行值加一。这样从斜角一直移动到一个点。如果最终没有找到目标元素则返回false。这种方法的时间复杂度为O(m + n),其中m, n分别为矩阵的行数和列数。
按照这种思路,代码的实现如下:
public class Solution { public boolean searchMatrix(int[][] matrix, int target) { int m = matrix.length, n = matrix[0].length, i = 0, j = n - 1; while(i >= 0 && i < m && j >= 0 && j < n) { if(matrix[i][j] == target) return true; else if(matrix[i][j] > target) j--; else i++; } return false; } }
binary search
除了上述的办法,如果我们仔细看问题的描述,还会发现一个方法。就是它每一行是递增的。而且每后面一行的第一个元素比前一行最后的元素要大。这说明如果我们把整个矩阵按照每行这么排列的展开,它就构成了一个排序的数组。而在一个排序的数组里找一个给定的元素,很显然,上二分搜索就搞定了。
public class Solution { public boolean searchMatrix(int[][] matrix, int target) { int m = matrix.length, n = matrix[0].length, start = 0, end = m * n -1; while(start <= end){ int mid = (start + end) / 2; int tempRow = (mid / n); int tempCol = (mid % n); if(matrix[tempRow][tempCol] == target) return true; else if(matrix[tempRow][tempCol] < target) start = mid + 1; else end = mid - 1; } return false; } }
相关推荐
leetcode上的题目,网站上测试通过,可以借鉴下
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 ...
* [Breadth-First Search](https://github.com/kamyu104/LeetCode#breadth-first-search) * [Depth-First Search](https://github.com/kamyu104/LeetCode#depth-first-search) * [Backtracking]...
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 ...
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 II 替换空格 从尾到头打印链表 重建二叉树 105. Construct Binary Tree from Preorder and Inorder Traversal 用两个栈实现队列 232. Implement Queue using Stacks 旋转数组的最小数字 153. ...
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 2 Useful Links 我的题解 刷题打卡活动 算法基础课 算法基础课笔记 基础算法 : 快速排序,归并排序 ...LeetCode分类复习清单 ...Search ...2D matrix] [] Slicing Window / Two Pointers [918 Ma
LeetCode判断字符串是否循环 LC 算法练习 LeetCode需要重点关注的题目 简单题型 中等难度题型 kth largest element in an array . use heap, use quick select. maximal square. Use dynamic programming. use just ...
leetcode 社交面试准备 问题类别: Array 二ptr/sliding window, 2d matrix, backtracking, DP, circle array,分治法 String reverse, palindrome, Sliding window, backtracking Lists medium, reverse, merge Tree...
这是我准备面试时建议的个人问题清单。... https://leetcode.com/problems/search-a-2d-matrix/ https://leetcode.com/problems/set-matrix-zeroes/ 弦乐 https://leetcode.com/problems/positions-of-large-g
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 ...
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