陈中正的网络日志

LeetCode: Search a 2D Matrix

题目

https://oj.leetcode.com/problems/search-a-2d-matrix/

分析

用二分查找来解决这道题:

第一次二分查找在第一列中找到那个数所在的那一行,第二次二分查找在那一行中找出那个数。

时间复杂度是O(log(m)) + O(log(n))

一开始想不出第一次二分查找应该怎么写,即找出第一个比target小的那个数,

后来看了参考中的解法才明白,二分查找退出的那一时刻,如果arr[mid] != target,那么arr[l] 是第一个比target大的数,arr[r]是第一个比target小的数。

代码

class Solution
{
public:
    bool searchMatrix(vector<vector<int>> &matrix, int target)
    {
        int h = matrix.size();
        int w = matrix[0].size();


        int l = 0;
        int r = h - 1;
        while (l <= r)
        {
            int mid = (l + r) >> 1;
            if (matrix[mid][0] < target)
                l = mid + 1;
            else if (matrix[mid][0] > target)
                r = mid - 1;
            else
                return true;
        }

        int row = r;
        if (row < 0)
            return false;

        l = 0;
        r = w - 1;
        while (l <= r)
        {
            int mid = (l + r) >> 1;
            if (matrix[row][mid] < target)
                l = mid + 1;
            else if (matrix[row][mid] > target)
                r = mid - 1;
            else
                return true;
        }
        return false;
    }
};

参考

http://blog.csdn.net/linhuanmars/article/details/24216235

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40920131

Categories:  OJ题解 

« LeetCode: Partition List LeetCode: Edit Distance »