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

题目描述

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

测试用例

• 功能测试（输入的数组中存在一个出现次数超过数组长度一半的数字；输入的数组中不存在一个出现次数超过数组长度一半的数字）
• 特殊输入测试（输入的数组中只有一个数字；输入空指针）

题目考点

• 考察应聘者对时间复杂度的理解。应聘者每想出一种解法，面试官都期待他能分析出这种解法的时间复杂度是多少。
• 考察应聘者思维的全面性。面试官除了要求应聘者能对有效的输入返回正确的结果，同时也期待应聘者能对无效的输入进行相应的处理。

解题思路

直接解法

先排序，如果存在出现次数大于数组长度一半的数，那么这个数必然在n/2位置上

排序的时间复杂度为O(nlogn)

HashMap解码

利用HashMap来统计数字出现的次数

时间复杂度不为O(1)

基于Partition函数的时间复杂度为O(n)的算法

当数组中有一个数字出现的次数超过了数组长度的一半，那么这个数字一定是数组的中位数。

我们利用Partition函数找到中位数，然后判断这个数出现的次数是否真的超过数组长度的一半，如果是就输出这个数，不然就不存在超过数组长度一半的数，返回0。

代码太长，这里就不写了，可以参考之前的快速排序的Partition算法。

这种方法不好的地方是会修改输入的数组。

根据数组特点找出时间复杂度为O(n)的算法

首先要明确一点：如果数组中一个数字出现的次数超过数组长度的一半，那么这个数字出现的次数比其他所有数字出现的次数之和还要多。

我们可以在遍历数组的时候保存两个值：一个是数组中的一个数字，一个是该数组出现的次数。当我们遍历到下一个数字的时候，如果下一个数字和我们之前保存的数字相同，则次数加1；如果下一个数字和我们之前保存的数字不同，则次数减1。如果次数为0，那么我们需要保存下一个数字，并把次数设为1，由于我们要找的数字出现的次数比其他所有数字出现的次数之和还要多，那么要找的数字肯定是最后一次把次数设为1时对应的数字。

这其实是一个投票问题，见补充。

自己解题

/**
 * 数组中出现次数超过一半的数字
 *
 * @Author rex
 * 2018/8/15
 */
public class Solution {
    /**
     * 基于HashMap的解法
     * 时间复杂度为O(1)
     * 空间复杂度不为O(1)
     * @param array
     * @return
     */
    public int moreThanHalfNum_Solution(int [] array) {
        if (array == null || array.length == 0) {
          return 0;
        }
        Map<Integer, Integer> map = new HashMap<>();
        int value;
        for (int i = 0; i < array.length; i++) {
            if (!map.containsKey(array[i])) {
                map.put(array[i],1);
                if (array.length == 1) {
                    return array[0];
                }
            } else {
                value = map.get(array[i]);
                value = map.put(array[i], value + 1);
                if (value + 1 > array.length/2) {
                    return array[i];
                }
            }
        }
        return 0;
    }
}

解法缺陷：

空间复杂度不为O(1)

参考解题

/**
 * 数组中出现次数超过一半的数字
 *
 * @Author rex
 * 2018/8/15
 */
public class Solution1 {
    /**
     * 基于数组特点解法
     * 投票问题
     * @param array
     * @return
     */
    public int moreThanHalfNum_Solution(int [] array) {
        if (array == null || array.length == 0) {
            return 0;
        }
        int result = array[0];
        int times = 1;
        for (int i = 1; i < array.length; i ++) {
            if (times == 0) {
                result = array[i];
                times = 1;
            }

            if (array[i] == result) {
                times++;
            } else {
                times--;
            }
        }
        if (checkMoreThanHalf(array,result)) {
            return result;
        } else {
            return 0;
        }


    }

    /**
     * 检查result是不是在array出现次数超过一半
     * @param array
     * @param result
     * @return
     */
    public boolean checkMoreThanHalf(int[] array, int result) {
        boolean isMoreThanHalf = false;
        int times = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] == result) {
                times++;
            }
        }
        if (times > (array.length >> 1)) {
            isMoreThanHalf =true;
        }
        return isMoreThanHalf;

    }
}

补充

1. Boyer-Moore Majority Vote