[剑指Offer] 二维数组中的查找

2021-01-14 12:13

阅读：656

标签：函数移动算法复杂度需要 pre als 二维 class amp

问题描述

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

分析

抛开二维数组的有序性质，直接遍历二维数组找是否含有一个数，算法复杂度为\(O(n^2)\)

bool Find(int target, vector > array) {
    for(int i = 0; i

二位数组的每一行都是递增的，可以对每一行进行二分查找，算法复杂度为\(O(nlogn)\)

 bool Find(int target, vector > array) {
    for(int i = 0; i  array[i][mid]) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
    }

    return false;
}

考虑到二维数组的列也是有序的，选择一个初始点，与target比较

> target, 则target在该初始点左上

只有左下和右上两个点才能作为起始点，其他点会导致移动的方向不确定（如以v[0][0]为初始点时，当v[0][0]

技术图片

用这种方法，每次可以使问题的规模减少一行或者一列，找到array[p][q]需要p+q+1次

bool Find(int target, vector> array) {
    int row = array.size()- 1, col = 0;
    while (row >= 0 && col  target) {
            --row;
        } else {
            ++col;
        }
    }

    return false;
}

[剑指Offer] 二维数组中的查找

标签：函数移动算法复杂度需要 pre als 二维 class amp

原文地址：https://www.cnblogs.com/arcsinw/p/12941520.html

上一篇：Springboot中如何设置不同的开发环境

下一篇：Jupyter Notebook 使用R语言的设置方法

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：[剑指Offer] 二维数组中的查找
文章链接：http://soscw.com/index.php/essay/41771.html

亲，登录后才可以留言！

[剑指Offer] 二维数组中的查找

问题描述

分析

评论

热门文章

推荐文章

最新文章

置顶文章