面试算法代码知识梳理系列

面试算法知识梳理(1) - 排序算法
面试算法知识梳理(2) - 字符串算法第一部分
面试算法知识梳理(3) - 字符串算法第二部分
面试算法知识梳理(4) - 数组第一部分
面试算法知识梳理(5) - 数组第二部分
面试算法知识梳理(6) - 数组第三部分
面试算法知识梳理(7) - 数组第四部分
面试算法知识梳理(8) - 二分查找算法及其变型
面试算法知识梳理(9) - 链表算法第一部分
面试算法知识梳理(10) - 二叉查找树
面试算法知识梳理(11) - 二叉树算法第一部分
面试算法知识梳理(12) - 二叉树算法第二部分
面试算法知识梳理(13) - 二叉树算法第三部分

---

一、概要

本文介绍了有关数组的算法第一部分的Java代码实现，所有代码均可通过 在线编译器 直接运行，算法目录：

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

二、代码实现

2.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 <= maxx && miny <= maxy){
            //如果最小的元素(左上角)大于d，或者最大的元素(右下角)小于d，那么可以确定矩阵中不存在p。
            if (p[minx][miny] > d|| p[maxx][maxy] < d)
                return false;
            //如果右上角的元素和p直接相等，那么直接返回。
            if (d == p[minx][maxy]) {
                return true;
            }
            //不断缩小矩形的范围。
            while (p[minx][maxy] > d) //从右上角的第一个元素，从右往左，找到第一个不大于d的元素。
                maxy -= 1;
            while (p[minx][maxy] < d) //从右上角的第一个元素，从上到下，找到第一个不小于d的元素。
                minx += 1;
        }
        return false;
    }
    public static void main(String[] args) {
        int p[][] = { {1, 2, 8, 9}, {2, 4, 9, 12}, {4, 7, 10, 13}, {6, 8, 11, 15}};
        System.out.println("result=" + searchMisInt(p, 10, 3, 3));
    }
}

运行结果：

>> result=true

2.2 获得旋转数组中的最小数字

问题描述

把一个数组最开始的若干个元素搬到数组的末尾，称为数组的旋转。现在输入一个递增序列的旋转数组，输出旋转数组的最小值，例如{1, 2, 3, 4, 5}的一个旋转数组为{3, 4, 5, 1, 2}，最小值为1。

解决思路

加入经过旋转后的数组不等于它本身，那么这个旋转后的数组有一个特点：它以最小值作为分界点被分为两个部分，不包含最小值的前半部分是有序的，包含最小值的后半部分也是有序的，因此我们可以借助 二分查找 的思想。

首先获得当前数组的中点位置pMid：

• 如果pMid的数值 大于等于 首节点pStart的数值，那么说明 pMid 位于前半部分数组中，因此可以确定最小值在[pMid, pEnd]之间
• 如果pMid的数值 小于等于 末节点pEnd的数值，那么说明 pMid 位于后半数组当中，而pMid是[pMid,pEnd]之间最小的元素，因此可以确定最小值在[pStart, pMid]之间。
• 通过以上两步骤，不断缩小数组的范围，直到缩小后的数组只有两个元素为止，第二个元素的值就是我们要找的最小值。

实现代码

class Untitled {

    static int rotateMinIndex(int p[], int length){
        if (length == 1) {
            return 0;
        }
        
        int pStart = 0;
        int pMid = 0;
        int pEnd = length-1;
        
        if (p[pStart] < p[pEnd]) {
            return pStart;
        }
        while (pStart < pEnd - 1) {
            pMid = (pStart + pEnd) >> 1;
            if (p[pStart] == p[pMid] && p[pMid] == p[pEnd])
                return rotateMinIndexOrder(p, pStart, pEnd);
            if (p[pMid] >= p[pStart]) //左边数组是有序的，最小点在右边
                pStart = pMid;
            else if(p[pMid] <= p[pEnd]) //右边数组是有序的，最小点在左边
                pEnd = pMid;
        }
        
        if (p[pStart] > p[pEnd])
            return p[pEnd];
        
        return -1;
    }

    static int rotateMinIndexOrder(int p[], int pStart, int pEnd){
        for(int i = pStart; i < pEnd; i++){
            if (p[i+1] < p[i])
                return i+1;
        }
        return pEnd;
    }

    public static void main(String[] args) {
        int p[] = {3, 4, 5, 1, 2};
        System.out.println("result=" + rotateMinIndex(p, 5));
    }
}

运行结果

>> result=1

2.3 调整数组使奇数位于偶数之前

问题描述

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

解答思路

通过两个变量pStart、pEnd分别记录从首节点和末节点开始扫描的下标，pStart从首节点向末节点开始扫描，如果找到一个偶数，那么停止扫描，让pEnd从末节点向首节点开始扫描，直到找到一个奇数，然后和pStart所指向的偶数交换，这样就能保证[0, pStart]之间的都是奇数，而[pEnd, len-1]之间的都是偶数。

完成交换后，再开始移动pStart寻找下一个偶数，重复上面的操作，直到pStart和pEnd相遇，就可以满足问题的要求了。

实现代码

class Untitled {
    
    static void printArray(int p[]) {
        for (int i = 0; i < p.length; i++) {
            System.out.print(p[i] + ",");
        }
    }

    static void reverseOddEven(int p[], int length){
        int i = 0;
        int j = length-1;
        int t;
        while (true) {
            /*i指向数组length，或指向一个偶数*/
            while (i < length && p[i] % 2 != 0)
                i++;
            /*j指向-1，j指向一个奇数，j的值小于i*/
            while (j >= 0 && (p[j] % 2 == 0) && j >= i)
                j--;
            if (i > j)
                break;
            t = p[i]; p[i] = p[j]; p[j] = t;
        }
    }

    public static void main(String[] args) {
        int p[] = {3, 4, 5, 1, 2};
        reverseOddEven(p, p.length);
        printArray(p);
    }
}

运行结果：

>> 3,1,5,4,2,

2.4 找出数组中出现次数超过一半的数字

问题描述

找出数组中出现次数超过一半的数字

解决思路

将整个数组中的元素看成两类：出现次数超过一半的数字 和 其余数字。利用一个辅助的变量time和d，初始时候将d设为p[0]，time设为1，开始从头开始遍历数组。

实现代码

class Untitled {

    static Boolean verifyMoreThanHalf(int p[], int data, int length){
        int time = 0;
        for (int i = 0; i < length; i++) {
            if(p[i] == data)
                time++;
        }
        if ((time << 1) >= length)
            return true;
        return false;
    }

    static void moreThanHalf(int p[], int length) {
        //初始化
        int d = p[0];
        int time = 1;
        //从第二个元素开始遍历。
        for (int i = 1; i < length; i++) {
            if(time == 0){
                d = p[i];
                time = 1;
            }else if(d == p[i])
                time += 1;
            else
                time -= 1;
        }
        if (verifyMoreThanHalf(p, d, length)) {
            System.out.println("出现次数超过一半的元素=" + d);
        } else {
            System.out.println("没有次数超过一半的元素");
        }
        
    } 
    public static void main(String[] args) {
        int p[] = {1, 2, 3, 2, 2, -1, 2, 2, 8, 2, 2};
        moreThanHalf(p, p.length);
    }
}

运行结果

>> 出现次数超过一半的元素=2

---

更多文章，欢迎访问我的 Android 知识梳理系列：

• Android 知识梳理目录：http://www.jianshu.com/p/fd82d18994ce
• 个人主页：http://lizejun.cn
• 个人知识总结目录：http://lizejun.cn/categories/