`
up2pu
  • 浏览: 217637 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

面试题3:二维数组中的查找

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


分析:
1 2  8  9
2 4  9 12
4 7 10 13
6 8 11 15

以查找7为例,从右上角开始:
1.9大于7,下一次只需要在9的左边区域查找
2.8大于7,下一次只需要在8的左边区域查找
3.2小于7,下一次只需要在2的下边区域查找
4.4小于7,下一次只需要在4的下边区域查找


代码:
bool Find(int* matrix, int rows, int columns, int number)
{
    bool found = false;
    if(matrix != NULL && rows > 0 && columns > 0)
    {
        int row = 0;
        int column = columns - 1;
        while(row < rows && column >= 0)
        {
            if(matrix[row * columns + column] == number)
            {
                found = true;
                break;
            }
            else if(matrix[row * columns + column] > number)
                -- column;
            else
                ++ row;
        }
    }
    return found;
}


package net.ecoolsoft.question;

public class SearchInArray {
	/**
	 * 在一个二维数组中,每一行都按照从左到右递增的顺序排序,
	 * 每一列都按照从上到下递增的顺序排序。请完成一个函数,
	 * 输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
	 * @param data 数组
	 * @param key 要查找的数字
	 * @return	找到返回true,未找到返回false
	 */
	public boolean findInArray(int[][] data, int key) {
		if(data == null || data.length == 0) {
			return false;
		}
		int i = 0;
		int j = data[0].length-1;
		while(i<data.length && j>=0) {
			if(data[i][j] == key) {
				return true;
			} else if(data[i][j] > key) {
				j--;
			} else {
				i++;
			}
		}
		return false;
	}
}


package net.ecoolsoft.question;

import junit.framework.Assert;

import org.junit.Test;

public class SearchInArrayTest {
	@Test
	public void findInArrayFailedTest() {
		int[][] data = {{1,2,8,9}, {2,4,9,12}, {4,7,10,13}, {6,8,11,15}};
		int key = 14;
		SearchInArray sArray = new SearchInArray();
		boolean result = sArray.findInArray(data, key);
		Assert.assertFalse(result);
	}
	
	@Test
	public void findInArrayTest() {
		int[][] data = {{1,2,8,9}, {2,4,9,12}, {4,7,10,13}, {6,8,11,15}};
		int key = 11;
		SearchInArray sArray = new SearchInArray();
		boolean result = sArray.findInArray(data, key);
		Assert.assertTrue(result);
	}
}


参考资料:《剑指Offer——名企面试官精讲典型编程题》
分享到:
评论

相关推荐

    wyh317#JZoffer#面试题4:二维数组中的查找1

    测试用例特殊输入测试(空指针)二维数组包括要查找的数字(target为数组最大值、target为数组最小值、target位于数组最大值和最小值之间)二维数组不包

    剑指Offer(Python多种思路实现):二维数组中的查找

    剑指Offer(Python多种思路实现):二维数组中的查找 面试4题: 题目: 在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个...

    java基础面试题二维数组中查找

    java基础面试题二维数组中查找本资源系百度网盘分享地址

    剑指offer(java版67题)

    面试题 1:二维数组中的查找(考点: 数组) 1 面试题 2:替换空格(考点: 字符串) 2 面试题 3:从尾到头打印链表(考点: 链表) 2 面试题 4:重建二叉树(考点: 树) 4 面试题 5:用两个栈实现队列(考点: 栈和...

    练习题4-二维数组中的查找.cpp

    在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个证书,判断数组中是否含有该整数。C语言完整代码。.cpp格式

    【剑指offer】面试题4-二维数组中的查找-完整的可执行代码(Java)

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

    jianzhi-offer:剑指offer面试题-javascript版源码与测试用例

    面试题03:二维数组中的查找 面试题06:重建二叉树 面试题08:旋转数组中的最小数 面试题10:二进制中1的个数 面试题14:调整数组顺序使奇数位于偶数前面 面试题18:树的子结构 面试题20:顺时针打印矩阵 面试题21:...

    leetcode迷宫问题-LeetCode:LeetCode刷题之剑指offer系列

    面试题04:二维数组中的查找 +2 有序矩阵查找 面试题05:替换空格 +2 查找 面试题06:从尾到头打印链表 +2 栈+双数组 面试题07:重建二叉树 +2 递归 面试题09:用两个栈实现队列 +2 双栈 面试题10 - I:斐波那契数列...

    leetcode二维数组-programming_exercises:leetcode、nowcoder刷题之路

    二维数组中的查找: 替换空格: 从尾到头打印链表: 重建二叉树: 用两个栈来实现队列: 旋转数组的最小数字: 斐波那契数列: 跳台阶: 跳台阶2: 矩形覆盖: 二进制中1的个数 数值的整数次方: 调整数组顺序,使奇数位于偶数...

    剑指offer之python实现

    面试题3 二维数组中的查找 面试题4 替换空格 面试题5 从尾到头打印单链表 面试题6 重建二叉树 面试题7 用两个栈实现队列 2.4 算法和数据操作 面试题8 旋转数组的最小数字 面试题9 斐波那契数列 面试题10 二进制中1的...

    为面试做准备的python经典编程题之1

    二维数组中的查找.py 替换空格.py 从尾到头打印链表.py 重建二叉树.py 二叉树的下一个节点.py 用两个栈实现队列.py 菲波那切数列.py 旋转数组的最小数字.py 矩阵中的路径.py 机器人的运动范围.py 剪绳子.py 二进制中...

    javalruleetcode-play-leetcode:用程序解决leetcode的算法问题

    二维数组中的查找 面试题05 替换空格 面试题06 从尾到头打印链表 面试题07 重建二叉树 面试题09 用两个栈实现队列 面试题10- I 斐波那契数列 面试题10- II 青蛙跳台阶问题 面试题11 旋转数组的最小数字 面试题12 ...

    leetcode中国-LeetCode:力扣(leetcode-cn)题解,大部分使用C++实现,少量使用Golang实现

    二维数组中的查找 easy 面试题68-I 二叉搜索树的最近公共祖先 easy 面试题68-II 二叉树的最近公共祖先 easy LeetCode # 题目 难度 题解 1 两数之和 easy 2 两数相加 medium 3 无重复字符的最长子串 medium 5 最长...

    leetCode 面试高频算法整理-2020

    2020高频面试算法整理 leetcode ,18个大类,80+...数组|1)乘积最大子序列|2)求众数|3)旋转数组|4)存在重复元素|5)移动零|6)打乱数组|7)两个数组的交集 II|8)递增的三元子序列|9)搜索二维矩阵 II|10)除自身以外数组的乘

    CodingQuestion:编码面试题,数据结构库

    数组和矩阵(二维数组或更高维数组) 细绳 链表 树 回溯 DFS和BFS 二元搜寻 动态编程 图形 拓扑排序 堆栈和优先级队列 特里 联合查找 其他(算法与设计): 位操作 数学 随机的 设计 计划: 数组(两个指针,排序,...

    数据结构和算法:使用C ++ STL,Python,Lisp的实现

    二维阵列Q1。 在Minesweeper中分配编号。 Q2。 查找在Minesweeper中扩展的位置。 Q3。 将矩阵旋转90度。 Q4。 将矩阵就地旋转90度。 ...弦乐Q1。 查找非重复字符。 Q2。 找出两个字符串是否在一次编辑中。 ...链表和...

    leetcode卡-LeetCode:LeetCode相关记录

    leetcode卡 LeetCode 每日一练 时间 序号 题目 03-01 P225 用队列实现栈 03-02 ...面试题10.01 ...面试题01.06 ...二维数组中的查找 05 替换空格 06 从尾到头打印链表 07 重建二叉树 09 用两个栈实现队列 12

    最低加油次数leetcode-LeetCode:LeetCode刷题笔记

    知识点:二分查找,查找给定target在排序数组中出现的左右边界 990. 等式方程的可满足性 知识点:并查集、包含小写字母的字符串的处理 Day32 面试题46. 把数字翻译成字符串 知识点:动态规划,一维动态规划,dp[i]...

    LeetCode解题总结

    7.3 在二维排序数组中查找给定值 7.4 在旋转有序数组中查找最小值 7.4.1 数组无重复 7.4.2 数组有重复 7.5 在旋转排序数组中查找指定数字 8. 暴力枚举法 8.1 求集合的子集 8.2 集合的全排列 8.3 在指定树中选择进行...

    javalruleetcode-Leetcode:LeetCode、Swordoffer、数据结构、算法的编程题

    二维数组的查找 so.13.调整数组顺序使奇数位于偶数前面 so.19.顺时针打印矩阵 so.28.数组中出现次数超过一半的数字 so.32.把数组排成最小的数 so.35.数组中的逆序对 so.40.数组中只出现一次的数字 so.41.和为S的连续...

Global site tag (gtag.js) - Google Analytics