LeetCode | 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.

    分析

    原来做过:九度Online Judge | 剑指offer | 题目1384:二维数组中的查找,文中给出了大牛的链接。

    解法1:二分法

    解法2:从右上或左下开始搜索,以右上为例,如果被搜索的元素大于target就减横坐标,如果小于target就减纵坐标,否则就是相等返回true

    解法1

    public class SearchA2DMatrix { public boolean searchMatrix(int[][] matrix, int target) { if (matrix == null || matrix.length == 0) { return false; } int M = matrix.length; int N = matrix[0].length; int low = 0; int high = M * N - 1; while (low target) { high = mid - 1; } else { low = mid + 1; } } return false; } }

    解法2

    public class SearchA2DMatrix { public boolean searchMatrix(int[][] matrix, int target) { if (matrix == null || matrix.length == 0) { return false; } int M = matrix.length; int N = matrix[0].length; int i = 0; int j = N - 1; while (i = 0) { if (matrix[i][j] == target) { return true; } else if (matrix[i][j] > target) { --j; } else { ++i; } } return false; } }

    点击复制链接 与好友分享!回本站首页
    您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力
    上一篇:全排列算法之非递归实现
    下一篇:Design Patterns----简单的工厂模式
    相关文章

    LeetCode题目9 Count and Say

    [LeetCode] Best Time to Buy an

    [leetcode]Implement strStr()

    leetcode代码分类汇总之-树

    [LeetCode]Convert Sorted Array t

    [LeetCode]Container With Most Water

    [LeetCode]Construct Binary Tree

    [LeetCode]Construct Binary Tree

    [LeetCode]Merge Sorted Array

    [LeetCode]Merge k Sorted Lists

    图文推荐

    LeetCode | Search a 2D Matrix
    ZOJ 3640 Help Me
    LeetCode | Search a 2D Matrix
    CF 518C(Anya and
    LeetCode | Search a 2D Matrix
    hdu 1016 Prime R
    UVA - 11987 - A
分类:默认分类 时间:2015-03-07 人气:1
本文关键词:
分享到:

相关文章

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.030 (s). 10 q(s)