这个题在笔试中经常会考到,这里做个总结。思路就是,从矩阵的最右上角的元素开始扫描a[i][j],如果要查找的数n小于该元素,则让i--,即往左移动一个数据再比较。如果n大于该数,则让j++,让原来的数往下移动一个数接着比较。 这里的设计思路就是充分利用了,数组横向纵向都递增的规律。而且巧妙的,一次只改变行数或列数,对应的列数或行数保持不变来进行搜索。
这和二维数组的螺旋打印异曲同工,待杂家有时间再总结螺旋打印问题。
时间复杂度最差为m+n,最好为m或者n。
程序如下:
#include <iostream>
using namespace std;
#define N 10
#define M 10
int main()
{
int a[N][M];
int n;
int i = 0, j = M-1;
while(i<N && j>=0)
{
if(n < a[i][j])
j--;
else if(n > a[i][j])
i++;
else
{
cout<<"已找到!i = "<<i<<"j = "<<j<<endl;
return 0;
}
}
return -1; //表示未找到
}
分享到:
相关推荐
通过二维数组实现,不是位操作,实现了一次迭代,东软的童鞋你们懂得...
C#的二维数组双线性插值算法。 用于二维数组的双线性插值算法,可分别设置长度和宽度。
php 笛卡尔积二维数组矩阵算法 生成多个组合 php 笛卡尔积二维数组矩阵算法 生成多个组合 php 笛卡尔积二维数组矩阵算法 生成多个组合 php 笛卡尔积二维数组矩阵算法 生成多个组合 php 笛卡尔积二维数组矩阵...
用数据结构与算法 实现的数组 用一维数组定义用 二维数组 定义三维数组 用模版
二维数组中的查找,逐行扫描,行内使用二分查找。最差情况需要扫描所有行,待完善
js代码-算法:二维数组随机打乱(扫雷)
53. 最大子数组和 给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 子数组 是数组中的一个连续部分。...如果算法调优不够,网站会在此测试用例报超时
用户输入2个二维数组,程序自动输出这2个数组的乘积
算法100%正确的程序. 几行几列,可在#define M,N中自行修改
给定一个二维数组,用C++实现将二维数组旋转90度,
C语言编写的杨辉三角,使用二维数组加上循环嵌套。是在学完二维数组后的经典练习题目,主要供给给初学C语言的同学参考是使用
分割数组算法分割数组算法分割数组算法分割数组算法分割数组算法分割数组算法
'仿制简单的SQL查询语句,用于对二维数组的查询 '参照SQL语句:Select * From array [Where conditions] [Distinct fields] [ResultWithTitle] ' '实现功能: ' 依条件设置查询数组,返回包含查询字段(或全部字段)...
1.掌握二维数组的定义、赋值和输入输出的方法; 2.掌握字符数组的使用; 3.掌握与数组有关的算法(例如排序算法)。
matlab模糊算法:4 单元数组深入学习.zip
基于二维数组和十字链表的Apriori算法 数组和链表.docx
基于二维数组和十字链表的Apriori算法 数组和链表(02).pdf
for(int row[] :arr) //此时不难看出,二维数组可以看作是每个元素都是一个一维数组的一维数组 { for(int item: row) { System.out.print(item+ " "); } System.out.println(); } 补充: //...
本篇只讨论基本的代码实现,由于只是对一维数组的聚类,距离公式上比较简单:distance = |a – b| 适合初学者理解最基本的原理 所谓一维数组 比如: [12, 3, 56, 89, 78, 2, 12, 45, 255, 236] 以下代码实现的是对一...