一、前言
本文介绍了有关数组的算法第一部分的 Java 代码实现,算法实例:
- 二维数组的整数查找
- 旋转数组中的最小数字(旋转数组中的最大数字)
- 调整数组使奇数位于偶数之前
- 找出数组中出现次数超过一半的数字
问题描述 在一个二维数组中,每一行都按照 从左到右递增的顺序,每一列都按照 从上到下递增的顺序 排序,编写一个函数,输入这样的一个二维数组和一个整数,判断该整数是否在二位数组中。
解决思路 首先要确定整数存在于数组的一个 前提条件:如果最小的元素(左上角)大于d,或者最大的元素(右下角)小于d,那么可以确定矩阵中不存在d。
这里需要关注一个特殊的点,二维数组右上角的元素d,如果以d所在的列将数组分为左右两个部分,那么 右边部分的所有元素都是大于d 的;而如果以d所在的行将数组分为上下两个部分,那么 上半部分的所有元素都是小于d 的。利用这一特性,我们 从数组的右上角 开始搜寻:
- 判断数组右上角元素是否就是查找的值
- 如果不是,先按x轴的反方向遍历,从 右至左找到第一个不大于d 的元素。
- 之后再按y轴的正方向遍历,从 上至下找到第一个不小于d 的元素
- 经过以上两步,会得到一个缩小后的矩阵,检查前提条件是否仍然满足,如果不满足,那么就说明p不存在于数组中,反之则从第一步开始重复。
实现代码
class Untitled {
static Boolean searchMisInt(int p[][], int d, int maxx, int maxy){
int minx = 0; int miny = 0;
while(minx
关注
打赏
最近更新
- 深拷贝和浅拷贝的区别(重点)
- 【Vue】走进Vue框架世界
- 【云服务器】项目部署—搭建网站—vue电商后台管理系统
- 【React介绍】 一文带你深入React
- 【React】React组件实例的三大属性之state,props,refs(你学废了吗)
- 【脚手架VueCLI】从零开始,创建一个VUE项目
- 【React】深入理解React组件生命周期----图文详解(含代码)
- 【React】DOM的Diffing算法是什么?以及DOM中key的作用----经典面试题
- 【React】1_使用React脚手架创建项目步骤--------详解(含项目结构说明)
- 【React】2_如何使用react脚手架写一个简单的页面?