《剑指offer》刷题笔记（数组）：二维数组中的查找

冷不防 2022-06-08 10:58 144阅读 0赞

# 《剑指offer》刷题笔记（数组）：二维数组中的查找 #

--------------------

*  **转载请注明作者和出处：[http://blog.csdn.net/u011475210][http_blog.csdn.net_u011475210]**
 *  **代码地址：[https://github.com/WordZzzz/CodingInterviewChinese2][https_github.com_WordZzzz_CodingInterviewChinese2]**
 *  **文章地址：[https://github.com/WordZzzz/Note/tree/master/AtOffer][https_github.com_WordZzzz_Note_tree_master_AtOffer]**
 *  **刷题平台：[https://www.nowcoder.com/][https_www.nowcoder.com]**
 *  **题  库：剑指offer**
 *  **编  者：WordZzzz**

--------------------

*  剑指offer刷题笔记数组二维数组中的查找
    
     *  前言
     *  题目描述
     *  解题思路
     *  C代码实现
        
         *  右上角
         *  二分遍历
     *  Python代码实现
        
         *  右上角
         *  遍历

## 前言 ##

## 题目描述 ##

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

## 解题思路 ##

首先选取数组中右上角的数字。如果该数字等于要查找的数字，查找过程结束；如果该数字大于要查找的数字，剔除这个数字所在的列；如果该数字小于要查找的数字，剔除这个数字所在的行。也就是说如果要查找的数字不在数组的右上角，则每一次都在数组的查找范围中剔除一行或者一列，这样每一步都可以缩小查找的范围，直到找到要查找的数字，或者查找范围为空。

当然，大家也可以制定自己的规则，建议从左下角或者右上角开始，因为如果直接随机选取数组中的一个数开始进行比较，剩下的区域会出现重合的现象，即所谓的岔路，不好操作。比如我用的右上角，那就一直用右上角的进行判断，进行比较后剔除一行或者一列。算法时间复杂度为O(m+n)。

还有人直接对每一行用二分法进行查找，算法时间复杂度为O(mlogn)。

## C++代码实现 ##

### 右上角 ###

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

### 二分遍历 ###

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

## Python代码实现 ##

### 右上角 ###

# -*- coding:utf-8 -*-
    class Solution:
        # array 二维列表
        def Find(self, target, array):
            # write code here
    
            row=len(array)
            col=len(array[0])
            if row > 0 and col > 0:
                i = 0
                j = col -1
                while i < row and j >= 0:
                    if array[i][j] == target:
                        return True
                    elif array[i][j] > target:
                        j = j - 1
                    else:
                        i = i + 1
            return False

### 遍历 ###

# -*- coding:utf-8 -*-
    class Solution:
        # array 二维列表
        def Find(self, target, array):
            # write code here
            n=len(array)
            flag='false'
            for i in range(n):
                if target in array[i]:
                    flag='true';
                    break
            return flag
    while True:
        try:
            S=Solution()
            # 字符串转为list
            L=list(eval(raw_input()))
            array=L[1]
            target=L[0]
            print(S.Find(target, array))
        except:
            break

**系列教程持续发布中，欢迎订阅、关注、收藏、评论、点赞哦～～(￣▽￣～)～**

**完的汪(∪｡∪)｡｡｡zzz**

[http_blog.csdn.net_u011475210]: http://blog.csdn.net/u011475210
[https_github.com_WordZzzz_CodingInterviewChinese2]: https://github.com/WordZzzz/CodingInterviewChinese2
[https_github.com_WordZzzz_Note_tree_master_AtOffer]: https://github.com/WordZzzz/Note/tree/master/AtOffer
[https_www.nowcoder.com]: https://www.nowcoder.com/