剑指Offer -- 二维数组中的查找（C++）

题目描述

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

对于有序数组，我们一般使用二分法进行目标查找，从而有效减少复杂度。在该题目中，我们可以将二维数组的每一行拆开，分别使用二分法。

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
       int row = array.size();
       int column = array[0].size(); 
       for (int i = 0; i < row; i++) {
           int low = 0;
           int high = column - 1;
           while (low <= high) {
               int mid = (low + high) / 2;
               if (target == array[i][mid]) return true;
               else if (target > array[i][mid]) low = mid + 1;
               else high = mid - 1;
           }
       }
       return false;
    }
};

不过，在该题目中，除了每一行都从左到右递增之外，每一列也都从上到下递增，上面的二分法只利用了第一个条件。对于题目所给的条件我们应充分利用，从而找出最简单的方法。
依旧秉持着“从中间点找一个数，再通过判断决定向哪边移动”的思想，我们可以以左下角或右上角为初始点。假如选取了左下角为第一个对比数，那么当该数大于target时，应向右移，当该数小于target时，应向上移。

从左下角开始查找，代码如下：

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

从右上角开始查找，代码如下：

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

顺便附上一个本地IDE测试版：

#include <iostream>
#include <vector>
using namespace std;

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

int main() {
    vector<vector<int> > array2d;
    vector<int> array;
    int row, column, temp, target;
    cin >> row >> column;
    for (int i = 0; i < row; i++) {
        array.clear();
        for (int j = 0; j < column; j++) {
            cin >> temp;
            array.push_back(temp);
        }
        array2d.push_back(array);
    }
    cin >> target;
    if (Find(target, array2d))
        cout << "目标存在" << endl;
    else
        cout << "目标不存在" << endl;
    return 0; 
}

最后编辑于：2018.04.23 22:32:37