`
SunnyYoona
  • 浏览: 361677 次
社区版块
存档分类
最新评论

[LeetCode]74.Search a 2D Matrix

 
阅读更多

【题目】

Write an efficient algorithm that searches for a value in anmxnmatrix. 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]
]

Giventarget=3, returntrue.

【思路一】

杨氏矩阵解法:

(1)如果数组中选取的数字刚好和查找的数字相等,查找结束,返回true

(2)如果数组中选取的数字小于查找的数字,根据排序规则,要查找的数字只能在当前选取的数字的右边。列数减一。

(3)如果数组中选取的数字大于查找的数字,根据排序规则,要查找的数字只能在当前选取的数字的下边。行数加一。

时间复杂度:O(m+n)

【代码】

    /*------------------------------------
    *   日期:2015-02-04
    *   作者:SJF0115
    *   题目: 74.Search a 2D Matrix
    *   网址:https://oj.leetcode.com/problems/search-a-2d-matrix/
    *   结果:AC
    *   来源:LeetCode
    *   博客:
    ---------------------------------------*/
    #include <iostream>
    #include <vector>
    #include <cstring>
    #include <algorithm>
    using namespace std;

    class Solution {
    public:
        bool searchMatrix(vector<vector<int> > &matrix, int target) {
            if(matrix.empty()){
                return false;
            }//if
            int row = matrix.size();
            int col = matrix[0].size();
            int x = 0,y = col - 1;
            // 杨氏矩阵解法从右上角元素开始
            while(x < row && y >= 0){
                if(matrix[x][y] == target){
                    return true;
                }//if
                else if(matrix[x][y] < target){
                    ++x;
                }//else
                else{
                    --y;
                }
            }//while
            return false;
        }
    };

    int main(){
        Solution s;
        int target = 3;
        vector<vector<int> > matrix = {{1,3,5,7},{10,11,16,20},{23,30,34,50}};
        bool result = s.searchMatrix(matrix,target);
        // 输出
        cout<<result<<endl;
        return 0;
    }



【思路二】

根据排序规则,我们可以把矩阵看成一个串联起来的一维数组。正好可以利用二分查找。

n*m矩阵转换为一维数组:matrix[x][y] -> a[x*m + y]

一维数组转换为矩阵:a[x] -> matrix[x / m][ x % m]

时间复杂度:O(nmlognm)

【代码二】

    /*------------------------------------
    *   日期:2015-02-04
    *   作者:SJF0115
    *   题目: 74.Search a 2D Matrix
    *   网址:https://oj.leetcode.com/problems/search-a-2d-matrix/
    *   结果:AC
    *   来源:LeetCode
    *   博客:
    ---------------------------------------*/
    class Solution {
    public:
        bool searchMatrix(vector<vector<int> > &matrix, int target) {
            if(matrix.empty()){
                return false;
            }//if
            int row = matrix.size();
            int col = matrix[0].size();
            int start = 0,end = row * col - 1;
            // 二分查找解法
            int mid,x,y;
            while(start <= end){
                mid = start + (end - start) / 2;
                x = mid / col;
                y = mid % col;
                if(matrix[x][y] == target){
                    return true;
                }//if
                else if(target > matrix[x][y]){
                    start = mid + 1;
                }//else
                else{
                    end = mid - 1;
                }//else
            }//while
            return false;
        }
    };








分享到:
评论

相关推荐

    leetcode_Search-a-2D-Matrix.zip_leetcode

    leetcode上的题目,网站上测试通过,可以借鉴下

    LeetCode最全代码

    * [Breadth-First Search](https://github.com/kamyu104/LeetCode#breadth-first-search) * [Depth-First Search](https://github.com/kamyu104/LeetCode#depth-first-search) * [Backtracking]...

    LeetCode C++全解

    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答案-leetcode-java:leetcode的Java代码

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

    LeetCode-NoteBook:docsifyjs

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

    Leetcode扑克-coding-interviews:编码面试

    Leetcode扑克 项目简介 该项目为《剑指Offer》题解 OnlineJudge 题目 个人建议能使用LeetCode还是尽量用LeetCode。因为LeetCode题目接口更为规范,而且测试数据也更为全面。 牛客网 LeetCode 二维数组中的查找 240. ...

    recommended-problems

    这是我准备面试时建议的个人问题清单。... https://leetcode.com/problems/search-a-2d-matrix/ https://leetcode.com/problems/set-matrix-zeroes/ 弦乐 https://leetcode.com/problems/positions-of-large-g

    lrucacheleetcode-Coding-Interview:编程面试

    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判断字符串是否循环 LC 算法练习 LeetCode需要重点关注的题目 简单题型 中等难度题型 kth largest element in an array . use heap, use quick select. maximal square. Use dynamic programming. use just ...

    leetcode2-LeetcodeNotes:LeetCode解决方案和一切

    leetcode 2 Useful Links 我的题解 刷题打卡活动 算法基础课 算法基础课笔记 基础算法 : 快速排序,归并排序 : 整数二分,浮点数二分 数据结构 搜索与图论 : Dijkstra, Bellman-Ford, SPFA, Floyd : 染色法、匈牙利...

    cpp-算法精粹

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

    4:二维数组中的查找(剑指offer第2版Python)

    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焦虑-Interview-Notes:采访笔记

    leetcode 社交面试准备 问题类别: Array 二ptr/sliding window, 2d matrix, backtracking, DP, circle array,分治法 String reverse, palindrome, Sliding window, backtracking Lists medium, reverse, merge Tree...

Global site tag (gtag.js) - Google Analytics