剑指offer 面试题3—二维数组中找数

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

基本思想:
首先选取数组中右上角的数字。如果等于要找的数字,结束。如果大于要找的数字,剔除这个数字所在的列;如果小于要找的数字,剔除这个数字所在的行。

public static boolean find(int[][] array, int number) {
        if (array == null || array.length == 0)
            return false;

        int column = array[0].length;
        int row = array.length;

        int i = 0, j = column - 1;

        while (i < row && j > 0) {
            if (array[i][j] == number) {
                return true;
            } else if (array[i][j] > number) {
                j--;
                continue;
            } else if (array[i][j] < number) {
                i++;
                continue;
            }
        }
        return false;
    }
时间: 2024-10-02 14:58:33

剑指offer 面试题3—二维数组中找数的相关文章

剑指offer系列之三十四:数组中的逆序对

题目描述 在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对.输入一个数组,求出这个数组中的逆序对的总数. 要找到数组中的逆序对,一种思路是每遍历到一个元素的时候就和后面的元素进行一一比较,这种算法的时间复杂度是O(n2),所以不是很理想.我们可以借鉴归并排序的思想,把数组划分为子数组,然后对每个子数组中的逆序对数进行统计,统计完成后再并到一个新的数组中进行统计,这样就化整为零,实现了高效统计.总计起来思路就是:首先把数组划分为子数组,然后统计子数组中的逆序对数,然后

剑指offer系列之四十九:数组中重复的数字

题目描述 在一个长度为n的数组里的所有数字都在0到n-1的范围内. 数组中某些数字是重复的,但不知道有几个数字是重复的.也不知道每个数字重复几次.请找出数组中任意一个重复的数字. 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是重复的数字2或者3. 此题的思路还是比较简单的,与之前找出只出现一次的数字的题目有些类似,基本思路还是创建一个Map容器,key是出现的数字,value则是该数字出现的次数.在遍历数组的过程中,只要容器中已经出现了该数字,那么就直接返回给数组,

剑指offer系列之六十二:数据流中的中位数

题目描述 如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值.如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值. 根据题目的意思,就是对数据流中的数据进行排序然后得到其中位数.要解决的关键问题是如何在读入数据的时候就对数据进行排序.实际上可以看成是插入排序算法的应用,可以维持一个List集合,保证每次读入数据集合中的数据都是排序的.基本思路是:从集合的第一个元素开始,依次比较与新读入的元素的大小关系,从而把新读入

剑指offer系列之三十九:数组中只出现一次的数字

题目描述 一个整型数组里除了两个数字之外,其他的数字都出现了两次.请写程序找出这两个只出现一次的数字. 先考虑只有只有一个数字出现一次的情况,因为其他数字只出现了两次,所以对这两个数字进行异或运算的时候,其结果是0,那么那个只出现一次的数字进行异或运算的时候,其结果必然不是0,所以可以利用这点找出那个只出现一次的数字.现在考虑有两个数字出现一次的情况,仍然借鉴上面的思路,因为只出现一次的那个数字的异或结果不是0,遍历整个数组进行异或运算的结果也肯定不是0,现在可以对该数右边第一个是1的位的位置作

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

题目 在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序.请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数. 思路 [算法系列之三十三]杨氏矩阵 代码 /*--------------------------------------- * 日期:2015-07-19 * 作者:SJF0115 * 题目: 5.二维数组中的查找 * 网址:http://www.nowcoder.com/books/coding-interviews/a

剑指offer系列之三:在二维数组中查找元素

题目描述: 在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序.请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数. 由于题目条件的成立,所以使得这道题可以使用对角线的方法完成,可以从右上角的元素考虑,如果目标查找元素小于右上角的元素,那么不可能在右上角元素所在的列,如果目标大于剩余列的右上角的元素,那么不可能在该右上角元素所在的行.依照这个规律,就可以完成目标元素的查找(参考剑指offer书中的思路).基于此,我写出如下的代码(已被

c-如何定义一个自增之后在二维数组中移动到下一行的指针?

问题描述 如何定义一个自增之后在二维数组中移动到下一行的指针? 如何定义一个自增之后在二维数组中移动到下一行的指针?如何定义一个自增之后在二维数组中移动到下一行的指针? 解决方案 自增是不能移动到下一行的,自增实现的是++, 解决方案二: 用二重数组,比如 int ** arr; arr += 第一维长度; 解决方案三: int a[m][n]={""}; *a+1;表示下一行; *(a+1):表示下一个元素位置. 若果now<n,移动到x行的当前位置:a[m*x+now]. 解

二维数组中的查找概述

这一题给跪,c++死活超时...后来main函数改成用c就好了... 算法: /* 题目描述: 在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序.请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数. 输入: 输入可能包含多个测试样例,对于每个测试案例, 输入的第一行为两个整数m和n(1<=m,n<=1000):代表将要输入的矩阵的行数和列数. 输入的第二行包括一个整数t(1<=t<=1000000):代表要查找的数字.

二维数组中的查找

题目描述 在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序.请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数. 解题思路 从右上角元素开始遍历,若小于目标,则删除整行:若大于目标,则删除整列.每次执行都会删除一行或一列,最多执行2n次. 实现代码 class Solution { public: bool Find(vector<vector<int> > array,int target) { int rend =