剑指Offer算法题-二维数组中的查找

题目描述

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

解答

这道题很容易想到O(n²)的解法：

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        for(int i = 0; i < array.size(); i++){
            for(int iter = array[i].size()-1; iter >= 0; iter--){
                if(array[i][iter] == target) return true;
                if(array[i][iter] < target) break;
            }
        }
        return false;
    }
};

由于每行元素是有序的，还可以用复杂度为O(nlogn)二分法

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        for(int i = 0; i < array.size(); i++){
            if(binary_search(array[i].begin(), array[i].end(), target))
                    return true;
        }
        return false;
    }
};

更好的解法可以接近线性时间复杂度，从右上角找起，如果当前值等于target，则返回true；如果当前值比target大，这个值可能在同行的前面，因此应在同行往前找。如果当前值比target小，说明这个值应该在当前值位置的左下方，则在同列往下找

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        int row = 0, col = array[0].size() - 1;
        while(row < array.size() && col >= 0){
            if(array[row][col] == target)
                return true;
            if(array[row][col] < target)
                row++;
            else    //array[row][col] > target
                col--;
        }
        return false;
    }
};