[28] 数组中出现次数超过一半的数字(简单)
[28] 数组中出现次数超过一半的数字(简单)

题目描述

数组中有一个数字出现的次数超过数组长度的一半(主元素、众数),请找出这个数字。
例如输入一个长度为 9 的数组 [1,2,3,2,2,2,5,4,2]。由于数字 2 在数组中出现了 5 次,超过数组长度的一半,因此输出 2。你可以假设数组是非空的,并且给定的数组总是存在多数元素。
1 <= 数组长度 <= 50000
输入:[1,2,3,2,2,2,5,4,2]
返回值:2
输入:[3,3,3,3,2,2,2]
返回值:3
输入:[1]
返回值:1

解题思路

排序法

首先对数组进行排序,如果存在主元素,则一定处于数组长度中一半的位置。将整个数组进行遍历计数,如果证实出计数大于数组长度的一半则为主元素。
/**
 * 排序法
 * T(2n) S(1)
 */
public int MoreThanHalfNum_Solution(int[] array) {
    Arrays.sort(array);
    int principal = array[array.length >> 1];
    int count = 0;
    for (int i : array) {
        if (i == principal) {
            count++;
        }
    }
    if (count > array.length >> 1) {
        return principal;
    }
    return -1;
}

哈希表

建立一个哈希表,然后依次遍历数组,每次先判断该元素是否在哈希表中,如果在则将当前元素对应的计数值 + 1,此时否则将该元素存入哈希表。
/**
 * 哈希表
 * T(n) S(n)
 */
public int MoreThanHalfNum_Solution(int[] array) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i : array) {
        int t = map.containsKey(i) ? map.get(i) + 1 : 1;
        if (t > (array.length >> 1)) {
            return i;
        }
        map.put(i, t);
    }
    return -1;
}

候选法

建立一个计数器,遍历整个数组,如果当前元素与候选元素相等,则计数器 + 1,否则 - 1。如果计数器等于 0 则说明该元素失去候选资格,下个元素成为新的候选元素。最后选出的候选元素不一定就是主元素,需要再次判断其出现次数是否确实大于数组长度的一半。
/**
 * 候选法
 * T(2n) S(1)
 */
public int MoreThanHalfNum_Solution(int[] array) {
    int principal = array[0];
    int count = 1;
    for (int i = 1; i < array.length; i++) {
        if (array[i] == principal) {
            count++;
        } else {
            if (--count == 0) {
                principal = array[i];
                count = 1;
            }
        }
    }
    count = 0;
    for (int i : array) {
        if (i == principal) {
            count++;
        }
    }
    return count > array.length >> 1 ? principal : -1;
}