《剑指Offer》--- 数据结构の数组篇Ⅰ

《剑指⭕ffer》面试题一

题目描述：

题目: 找出数组中重复的数字

       在一个长度为 n 的数组里的所有数字都在 0 ~ n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2，3，1，0，2，5，3}，那么对应的输出是重复的数字2或者3。

分析边界条件及测试用例：

1. 长度为 n 的数组里包含一个或多个重复的数字
2. 数组不包含重复的数字
3. 无效输入测试用例（长度为 n 的数组中包含0 ~ n-1 之外的数字）

代码实现：

public class Question {
    public static int getDuplicate(int[] arr){
        if (arr == null || arr.length <= 0) {
            System.out.println("数组输入无效！");
            return -1;
        }
        for (int a : arr) {
            if (a < 0 || a > arr.length - 1) {
                System.out.println("数字大小超出范围！");
                return -1;
            }
        }
        for (int i = 0; i < arr.length; i++) {
            int temp;
            while (arr[i] != i) {
                if (arr[arr[i]] == arr[i])
                    return arr[i];
                // 交换arr[arr[i]]和arr[i]
                temp = arr[i];
                arr[i] = arr[temp];
                arr[temp] = temp;
            }
        }
        System.out.println("数组中无重复数字！");
        return -1;
    }

    /**
     *数组为null
     */
    public void test1() {
        System.out.print("test1：");
        int[] a = null;
        int dup = getDuplicate(a);
        if (dup >= 0)
            System.out.println("重复数字为：" + dup);
    }

    /**
     *数组无重复数字
     */
    public void test2() {
        System.out.print("test2：");
        int[] a = { 0, 1, 2, 3 };
        int dup = getDuplicate(a);
        if (dup >= 0)
            System.out.println("重复数字为：" + dup);
    }

    /**
     *数组数字越界
     */
    public void test3() {
        System.out.print("test3：");
        int[] a = { 1, 2, 3, 4 };
        int dup = getDuplicate(a);
        if (dup >= 0)
            System.out.println("重复数字为：" + dup);
    }

    /**
     *数组带重复数字
     */
    public void test4() {
        System.out.print("test4：");
        int[] a = { 1, 2, 3, 2, 4 };
        int dup = getDuplicate(a);
        if (dup >= 0)
            System.out.println("重复数字为：" + dup);
    }

    public static void main(String[] args) {
        Question f = new Question();
        f.test1();
        f.test2();
        f.test3();
        f.test4();
    }
}

《剑指⭕ffer》面试题二

题目描述：

题目：二维数组中的查找

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

测试用例：

1. 二维数组中包含查找的数字（查找的数字是数组中的最大值和最小值，介于最大值和最小值之间）
2. 二维数组中没有查找的数字
3. 特殊输入测试

代码实现：

    /**
     * 利用二维数组由上到下，由左到右递增的规律，
     * 那么选取左下角或者右上角的元素a[i][j]与target进行比较，
     * 当target大于元素a[i][j]时，那么target必定在元素a所在行的右边,
     * 即j++；
     * 当target大于元素a[i][j]时，那么target必定在元素a所在列的上边,
     * 即i--；
     * 时间复杂度m+n
     *
     * @param target
     * @param matrix
     * @return
     */
public class Question1 {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix == null){
            return false;
        }
        int i = matrix.length - 1;
        int j = 0;
        while(i >= 0 && j < matrix[0].length){
            if (target < matrix[i][j]){
                i--;
            } else if(target > matrix[i][j]){
                j++;
            } else {
                return true;
            }
        }
        return false;
    }

    /*
    数字在二维数组中
     */
    public void text1(){
        System.out.print("test1：");
        int[][] a = new int[][]{{1, 2, 8}, {2, 4, 9}, {4, 7, 10}};
        searchMatrix(a,8);
        System.out.println("要查找的数字存在！");
    }

    /*
    数字不在二维数组中
     */
    public void text2(){
        System.out.print("test2: ");
        int[][] a = new int[][]{{1, 2, 8}, {2, 4, 9}, {4, 7, 10}};
        searchMatrix(a,6);
        System.out.println("要查找的数字不存在！");
    }

    public static void main(String[] args) {
        Question1 f = new Question1();
        f.text1();
        f.text2();
    }
}