【Java -- 算法】数组算法（一）

一、前言

本文介绍了有关数组的算法第一部分的 Java 代码实现，算法实例：

• 二维数组的整数查找
• 旋转数组中的最小数字（旋转数组中的最大数字）
• 调整数组使奇数位于偶数之前
• 找出数组中出现次数超过一半的数字

二、代码 1. 二维数组的整数查找

问题描述 在一个二维数组中，每一行都按照 从左到右递增的顺序，每一列都按照 从上到下递增的顺序 排序，编写一个函数，输入这样的一个二维数组和一个整数，判断该整数是否在二位数组中。

解决思路 首先要确定整数存在于数组的一个 前提条件：如果最小的元素(左上角)大于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