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

package Array;

/**
 * 二维数组中的查找
 * 在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。
 * 请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
 */
public class Solution11 {
    public static void main(String[] args) {
        Solution11 solution11 = new Solution11();
        int[][] arr = new int[][]{{1, 2, 3, 4, 5}, {2, 4, 7, 8, 10}};
        System.out.println(solution11.Find_2(7, arr));
    }

    /**
     * 每一行都按照从左到右递增的顺序排序,把每一行看作有序递增数组
     * 利用二分查找
     * 通过遍历每一行查找得到答案
     * 时间复杂度mlog(n)
     *
     * @param target
     * @param array
     * @return
     */
    public boolean Find_3(int target, int[][] array) {
        if (array == null || array.length == 0 || (array.length == 1 && array[0].length == 0)) return false;
        for (int i = 0; i < array.length; i++) {
            int begin = 0;
            int end = array[0].length - 1;
            while (begin <= end) {
                int mid = (begin + end) / 2;
                if (target > array[i][mid]) {
                    begin = mid + 1;
                } else if (target < array[i][mid]) {
                    end = mid - 1;
                } else {
                    return true;
                }
            }

        }
        return false;
    }

    /**
     * 利用二维数组由上到下,由左到右递增的规律,
     * 那么选取左下角或者右上角的元素a[i][j]与target进行比较,
     * 当target大于元素a[i][j]时,那么target必定在元素a所在行的右边,
     * 即j++;
     * 当target大于元素a[i][j]时,那么target必定在元素a所在列的上边,
     * 即i--;
     * 时间复杂度m+n
     *
     * @param target
     * @param array
     * @return
     */
    public boolean Find_2(int target, int[][] array) {
        if (array == null || array.length == 0 || (array.length == 1 && array[0].length == 0)) return false;
        int i = array.length - 1;
        int j = 0;
        while (i >= 0 && j <= array[0].length) {
            if (target > array[i][j]) {
                j++;
            } else if (target < array[i][j]) {
                i--;
            } else {
                return true;
            }
        }
        return false;
    }

    /**
     * 暴力
     * 时间复杂度mn
     *
     * @param target
     * @param array
     * @return
     */
    public boolean Find(int target, int[][] array) {
        if (array == null || array.length == 0 || (array.length == 1 && array[0].length == 0)) return false;
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array[0].length; j++) {
                if (target == array[i][j]) {
                    return true;
                }
            }
        }
        return false;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏我的技术专栏

数据结构图文解析之:直接插入排序及其优化(二分插入排序)解析及C++实现

19330
来自专栏Python小屋

详解Python中的生成器表达式(generator expression)

生成器表达式(generator expression)也叫生成器推导式或生成器解析式,用法与列表推导式非常相似,在形式上生成器推导式使用圆括号(parenth...

37060
来自专栏武培轩的专栏

Leetcode#1.Two Sum(两数之和)

题目描述 给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。 你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。 示例: 给定 nums ...

34870
来自专栏Bingo的深度学习杂货店

Q167 Two Sum II - Input array is sorted

Given an array of integers that is already sorted in ascending order, find two n...

29450
来自专栏编程理解

排序算法(六):希尔排序

希尔排序是对插入排序的一种改进,也叫递减增量排序,算法过程中通过对增量值的递减调整,形成每一个增量值对应的一个或多个待排序分组,分别对分组执行插入排序,最后调整...

71210
来自专栏WD学习记录

逆波兰表达式

15040
来自专栏前端小叙

javaScript实现归并排序

归并排序是一个O(nlogn)的算法,其基本思想就是一个分治的策略,先进行划分,然后再进行合并,下面举个例子。有这样一组数据: {5,4,1,22,12...

34180
来自专栏magicsoar

Effective Modern C++翻译(3)-条款2:明白auto类型推导

条款2 明白auto类型推导 如果你已经读完了条款1中有关模板类型推导的内容,那么你几乎已经知道了所有关于auto类型推导的事情,因为除了一个古怪的例外,aut...

198100
来自专栏猿人谷

C语言函数指针基础

本文写的非常详细,因为我想为初学者建立一个意识模型,来帮助他们理解函数指针的语法和基础。如果你不讨厌事无巨细,请尽情阅读吧。 函数指针虽然在语法上让人有些迷惑,...

450100
来自专栏C语言及其他语言

【优秀题解】题解 1178: 三进制小数

你的任务呢,是将一个有理数转换成三进制小数。“什么是三进制小数呢?”你一定会问,这很明白,就是以三为基(二进制数以2为基,而十进制数则以10为基)的小数。

12330

扫码关注云+社区

领取腾讯云代金券