套路

• 关键字：是否、存在与否
• 反向求解非常迅速的情况下，可以先用假设题目中的正确结果，然后很容易就可以通过反证法验证假设的结果是否正确

注意点

• 暂无

目录

• 数组中出现次数超过一半的数字
• 表示数值的字符串

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

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

• 最优解：这道题如果用快排，时间复杂度为 O(nlogn) ，不是最优解，这道题最优解时间复杂度为 O(n) 。采用反证法，即假设数组中有一个数字出现的次数超过数组长度的一半，那么数组中不同的数之间两两PK，相互抵消，最终那个出现次数超过一半的数一定能够胜出。如果没有元素留下，说明没有超过一半的数存在；如果有元素存活下来了，那么说明它具备超过一半元素所应该具备的特性，再对这个元素进一步确认是不是数组中超过一半的元素，即可得到最终答案。

public int MoreThanHalfNum_Solution(int [] array) {
    if (array == null || array.length == 0) {
        return 0;
    }
    // val 存放假定的目标数字；遍历的数若与假定的目标数字相同，则次数加1，否则次数减1
    int times = 1, val = array[0];
    for (int i = 1; i < array.length; i++) {
        if (times == 0) {
            times++;
            val = array[i];
        } else if (val == array[i]) {
            times++;
        } else {
            times--;
        }
    }
    // 验证 val 存放的假定目标数字是否满足出现次数大于数组长度一半的要求
    times = 0;
    for (int i = 0; i < array.length; i++) {
        if (array[i] == val) {
            times++;
        }
    }
    return times > array.length / 2 ? val : 0;
}

表示数值的字符串

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。

• 最优解1：反证法，先假定是数字类型字符串，不抛异常说明字符串可以表示数值，抛异常说明字符串不能表示数值。
• 最优解2：正则表达式

public boolean isNumeric(char[] str) {
    try {
        Double num = Double.valueOf(String.valueOf(str));
    } catch (NumberFormatException e) {
        return false;
    }
    return true;
}

public boolean isNumeric(char[] str) {
    return String.valueOf(str).matches("[\\+-]?[0-9]*(\\.[0-9]*)?([eE][\\+-]?[0-9]+)?");
}