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

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

方法一：哈希的方法，用一个map存放每个值出现的次数，遍历一遍，看有没有一个值的出现次数大于一半的

import java.util.*;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < array.length; i++) {
            if (!map.containsKey(array[i]))
                map.put(array[i], 1);
            else
                map.put(array[i], map.get(array[i]) + 1);
        }
        int ans = 0;
        for (Integer integer : map.keySet()) {
            if (map.get(integer) > array.length/2) {
                ans = integer;
                break;
            }
        }
        return ans;
    }
}

方法二：相消法

对于数组任意两个数字，如果不同则相互消去，最后如果有剩余，则再遍历一遍剩余的这个数在数组中出现的次数是否大于数组长度的一半

import java.util.*;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int cnt = 0;
        int pre = -1;
        for (int i = 0; i < array.length; i++) {
            if (array[i] != pre) {
                if (cnt == 0) {
                    cnt = 1;
                    pre = array[i];
                } else {
                    cnt--;
                    if (cnt == 0) 
                        pre = array[i];
                }
            } else {
                cnt++;
            }
        }
        int num = 0;
        if (cnt == 0) return 0;
        else {
            for (int i = 0; i < array.length; i++) {
                if (array[i] == pre)
                    num++;
            }
        }
        if (num > array.length/2) return pre;
        else return 0;
    }
}