数据结构与算法 - 实战：查找1

题目：给定一个长度为n的数组，给出一个算法，判定该数组中是否存在重复元素
方法一：蛮力法
穷尽搜索整个数组，检查是否存在重复元素。
对每一个输入元素，都要检查数组中是否存在与其具有相同值得元素。

/**
 * 
 * @param array 给定的数组
 */
public static void checkDuplicatesBruteForce(int[] array) {
    int length = array.length;
    int j = 0;
    for (int i = 0; i < length; i++) {
        for (j = i + 1; j < length; j++) {
            if (array[i] == array[j]) {
                System.out.println("存在重复元素" + array[i]);
                return;
            }
        }
    }
    System.out.println("不存在重复元素");
}

方法二相对给定的数组排序，排序后，值相等的元素相邻。检查相邻元素是否相同即可

public static void checkDuplicatesSorting(int[] array) {
    // 先对数组排序
    Sort.bubbleSortImproved(array);
    int length = array.length;
    for (int i = 0; i < length; i++) {
        if (array[i] == array[i + 1]) {
            System.out.println("存在重复元素" + array[i]);
            return;
        }
    }
    System.out.println("不存在重复元素");
}

 * 方法三
 * 假设数组中的元素都是取值范围在0~n-1的正数。对于每个元素A[i]，寻找索引为A[i]的数组元素。
 * 选择A[A[i]]且将其标记为-A[A[i]](求A[A[i]]的负数)。重复该过程，直到遇到的元素值已经为负数，说明存在重复元素。
 * 
 * 已数组A={3,2,1,2,2,3}为例
 * 初始时
 *      3   2   1   2   2   3
 *      ---------------------
 *      0   1   2   3   4   5
 * 在步骤1中，对A[abs(A[0])]求负，
 *      3   2   1   -2  2   3
 *      ---------------------
 *      0   1   2   3   4   5
 * 在步骤2中，对A[abs(A[1])]求负，
 *      3   2   -1  -2  2   3
 *      ---------------------
 *      0   1   2   3   4   5
 * 在步骤3中，对A[abs(A[2])]求负，
 *      3   -2  -1  -2  2   3
 *      ---------------------
 *      0   1   2   3   4   5
 * 在步骤4中，对A[abs(A[3])]求负，
 *      3   -2  -1  -2  2   3
 *      ---------------------
 *      0   1   2   3   4   5
 * 此时可以发现A[abs(A[3])]已经为负数。这表明该元素已经被访问两次。
 * 
 * 注意：
 * 该方法不适用于只读数组
 * 该方法仅适用于所有元素为正数的数组
 * 如果数组中的元素取值范围不在0~n-1，则可能出现异常

public static void checkDuplicates(int[] array) {
    int length = array.length;
    for (int i = 0; i < length; i++) {
        if (array[Math.abs(array[i])] < 0) {
            System.out.println("存在重复元素" + Math.abs(array[i]));
            return;
        } else {
            array[Math.abs(array[i])] = -array[Math.abs(array[i])];
        }
    }
    System.out.println("不存在重复元素");
}

题目：发现缺失的数：已知一个由n-1个取值范围在1~n的整数组成的列表。假设列表中没有重复的出现的整数，则列表的中缺失某个整数。
例子：数组 A={1,2,4,6,3,7,8}，由7个整数，范围在1~8，没有重复元素，缺失整数5

/**
 * 方法一
 * 对于每一个在1~n的正数，检查该数是否在给定的数组中
 * @param array 给定的数组
 * @return 缺失的整数
 */
public static int findMissingNumber1(int[] array) {
    int n = array.length + 1;
    boolean found;
    for (int i = 1; i <= n; i++) {
        found = true;
        for (int j = 0; j < array.length; j++) {
            if (array[j] == i) {
                found = false;
            }
        }
        if (found) {
            return i;
        }
    }
    return -1;
}

/**
 * 方法二
 * 对数组排序，再通过一次扫描即可找到缺失整数
 * @param array 给定的数组
 * @return 缺失的整数
 */
public static int findMissingNumber2(int[] array) {
    Sort.bubbleSortImproved(array);
    int i = 1;
    while (i == array[i - 1]) {
        i++;
    }
    if (i != array[i - 1]) {
        return i;
    }
    return -1;
}

/**
 * 方法三
 * 使用求和公式
 * 1.对于n个数求和，sum=n*(n+1)/2
 * 2.用sum减去输入序列的所有元素，结果就是缺失的数据
 * @param array 给定的数组
 * @return 缺失的整数
 */
public static int findMissingNumber3(int[] array) {
    int n = array.length + 1;
    int sum = n * (n + 1) / 2;
    for (int i = 0; i < array.length; i++) {
        sum -= array[i];
    }
    if (sum != 0) {
        return sum;
    } else {
        return -1;
    }
}

/**
 * 方法四
 * 如果数字的总和超出所允许的最大整数范围，则可能导致整数溢出而不能获得正确答案。
 * 1.对数组中的所有元素执行异或(XOR)操作，设异或后的结果为X
 * 2.对1~n的所有元素执行异或(XOR)操作，设异或后的结果为Y
 * 3.对X与Y异或可得到缺失的整数
 * @param array 给定的数组
 * @return 缺失的整数
 */
public static int findMissingNumber4(int[] array) {
    int n = array.length + 1;
    int X = 0;
    int Y = 0;
    for (int i = 0; i < array.length; i++) {
        X ^= array[i];
    }
    for (int i = 1; i <= n; i++) {
        Y ^= i;
    }
    return X^Y;
}

测试代码，敬请参考数据结构与算法(JAVA版)

29、数据结构与算法 - 实战：查找1