题目描述

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

解题思路

1，第一种，超过一半的数必然出现在递增数组中间，先排序，然后统计中间值次数
2，第二种，遍历每一个数出现的次数，放到map里，然后用次数和len/2比较
3，第三种，利用数组的特性，超过一半的数出现的总次数比其它所有数出现总次数还多，这样我们在遍历数组的时候第一个值为result,次数为1，遇到相同的次数加1，遇到不同的减1，次数为0时，重复上述过程，最后得出的数即是持有股份最多的，不一定超过一半，然后我们在遍历统计它出现的次数，超过一半就是。

代码实现

/** * */
package 数组;

import java.util.Arrays;
import java.util.HashMap;

/** * <p> * Title:MoreThanHalfNum * </p> * <p> * Description: * </p> * * @author 田茂林 * @data 2017年8月25日 下午5:13:34 */
public class MoreThanHalfNum {
    // ===========================================================排序取中间值，时间复杂度nlogn
    public static int moreThanHalfNumSort(int[] array) {
        if (array == null || array.length < 1) {
            return -1;
        }
        int len = array.length;
        Arrays.sort(array);
        int num = array[len / 2];
        int count = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] == num) {
                count++;
            }
        }
        if (count * 2 > len) {
            return num;
        } else {
            return 0;
        }
    }

    // ============================================================存放到hashmap里，时间复杂度为O（n）,空间复杂度为O（n）
    public static int moreThanHalfNum(int[] array) {
        if (array == null || array.length < 1) {
            return -1;
        }
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        // 给数组中所有数字标记出现次数
        for (int i = 0; i < array.length; i++) {
            if (map.containsKey(array[i])) {
                map.put(array[i], map.get(array[i]) + 1);

            } else {
                map.put(array[i], 1);
            }
        }
        int len = array.length;
        for (int i = 0; i < map.size(); i++) {
            if (map.get(array[i]) > len / 2) {
                return array[i];
            }
        }
        return 0;

    }

    // ============================================================根据数组特点，时间复杂度O（n）
    public static int moreThanHalfNumSuper(int[] array) {
        if (array == null || array.length < 1) {
            return -1;
        }
        int len = array.length;
        int count = 1;
        int result = array[0];
        for (int i = 1; i < array.length; i++) {
            if (count == 0) {
                result = array[i];
                count = 1;
            }
            if (result == array[i]) {
                count++;
            } else {
                count--;
            }
        } // 最后持有count值的result可能就是超过一半的（{ 1, 2, 3, 2, 2, 2, 5, 4, 2
            // }，也有可能小于一半{1,2，2,3,4}，但其是唯一候选人，股份最大的）
        // 遍历次数，如果次数超过一半，则说明是
        count = 0;

        for (int i = 0; i < array.length; i++) {
            if (array[i] == result) {
                count++;
            }
        }
        if (count * 2 > len) {
            return result;
        } else {
            return 0;
        }

    }

    public static void main(String[] args) {
        int[] array = { 1, 2, 3, 2, 2, 2, 5, 4, 2 };
        System.out.println(moreThanHalfNum(array));
        System.out.println(moreThanHalfNumSort(array));

    }

}